Relazione 2000 provvisoria del GNCS

Nel corso del 2000 sono iniziati 10 Progetti Speciali, che si protrarranno per la parte iniziale del 2001, intitolati:

-Metodi di ricostruzione di immagini

-Approssimazione e quadratura numerica in una o piu' dimensioni

-Metodi e algoritmi per problemi non lineari strutturati in ottimizzazione numerica e controllo

-Metodi numerici per equazioni iperboliche e cinetiche

-Algoritmi ABS per sistemi lineari diofantini e programmazione lineare ad interi

-Metodi computazionali nella modellizzazione probabilistica di attivita' neuronale

-Modellizzaziobe di processi con trasporto di massa in mezzi eterogenei

-Ricostruzione di superfici con Subdivision e Wavelets

-La grafica nell'approssimazione numerica

-Ricostruzione e restoration di immagini mediante uso di funzioni di raffinamento, wavelets e multiwavelets:

Si sono inoltre conclusi 7 Progetti Coordinati, iniziati nel 1999, di cui si riporta la descrizione dettagliata delle tematiche e, in allegato, le pubblicazioni prodotte.

1 - Progetto: Nuovi paradigmi di calcolo: linguaggi e modelli:

Principali temi della ricerca: Programmazione logica (semantiche categoriali per linguaggi logici estesi; analisi di proprieta' di programmi logici). Logica computazionale, Calcolo algebrico simbolico, Software Engineering (specifica di riconfigurazioni e di mobilita' di sistemi).

2 - Progetto: Teoria costruttiva delle funzioni e problemi connessi”

Principali temi della ricerca: Analisi multirisolutiva e multilivello , Approssimazioni con basi radiali , Approssimazione polinomiale e applicazioni, Funzioni speciali.

Analisi multirisolutiva e multilivello E' stata studiata una classe di operatori positivi, autoaggiunti con norma unitaria sullo spazio degli operatori lineari e continui in L². Tale classe, costruita a partire da una classe di funzioni di raffinamento, può essere rappresentata come operatore definente una analisi multirisolutiva. E` ben noto che attualmente gli operatori legati alla scomposizione dello spazio L² in somma diretta di sottospazi complementariamente ortogonali sono fra quelli maggiormente utilizzati in ambito applicativo. Una applicazione importante consiste in un metodo per la differenziazione numerica di funzioni bivariate. In tale lavoro, sulla base di un campione con configurazione qualsivoglia ed estratto da un processo stocastico con matrice di correlazione incognita, viene costruito lo stimatore del gradiente utilizzando come denoise un metodo basato sulla decomposizione ondina e gli operatori alle differenze.

Approssimazione con basi radiali e applicazioni Nella maggior parte dei modelli legati alla approssimazione numerica di funzioni, vengono utilizzati funzioni a base radiale. In questa classe cadono le ben note funzioni splines. Per questa particolare classe di funzioni sono stati studiati nel caso bidimensionale gli operatori splines quasi interpolanti locali definiti su triangolazioni di tipo due uniformi e non.

Sono inoltre stati studiati condizioni di tipo hermitiano classi di splines interpolanti, metodi per la costruzione di curve soddisfacenti a parametri di forma, schemi astratti per la costruzione di curve sottoposte a vincoli locali e applicazioni nell’ambito della costruzione di integrali singolari e ipersingolari. In letteratura troviamo altre funzioni di tipo radiale, quali ad esempio quelle costruite con l’interpolazione alla Shepard. Tali funzioni sono particolarmente studiate in ambito applicativo con risultati riguardanti il loro utilizzo per l’individuazione e la successiva ricostruzione di funzioni 2D che presentano discontinuita` (faglie). Cio` viene fatto mediante un campione di dati esatti di grande dimensione. Inoltre, sono state sviluppate applicazioni a problemi reali come l’approssimazione della funzione potenziale di un campo newtoniano generato da una distribuzione continua di masse.

Approssimazione polinomiale. E` stata studiata una caratterizzazione della migliore approssimazione pesata in norma Lp con 1£p£¥ e con pesi aventi zeri interni agli intervalli (-1,1)o (-¥,+¥). In aggiunta, sempre nell’ambito dell’approssimazione polinomiale, sono stati individuati metodi numerici per equazioni d’integrali singolari e di integrali generalizzati.

Funzioni speciali Da molti anni e` attiva in Italia una scuola che ha come obiettivo lo studio di disuguaglianze sempre piu` stringenti per funzioni speciali. In particolare in questo anno sono state trovate disuguaglianze molto stringenti per il primo zero positivo delle funzioni di Bessel di prima specie. Inoltre si e` anche dimostrato che da ben noti risultati per i casi classici e` possibile ricavare molte famiglie di funzioni generatrici bilineari o multilaterali per i polinomi di Laguerre modificati. Accanto a questa attivita` di ricerca, va segnalata l’attivita` di collaborazione con ricercatori altamente qualificati a livello internazionale. La presenza di tali studiosi ha prodotto altresì una piu` stretta collaborazione che ha gia` dato i primi risultati

Con il Prof. Milovanovic e` stato messo a punto un lavoro che fornisce stime dell’errore per l’integrazione di funzioni periodiche sulla retta reale. Mentre con il Prof. Dieci sono state migliorate le approssimazioni di Pade` di matrici particolari. I ricercatori che lavorano nell’ambito del CAGD hanno sviluppato con il Prof. Farouki la ricerca di una nuova riparametrizzazione per funzioni lineari a tratti e razionali di primo grado di classe C0 e C1. Inoltre nell’ambito delle curve splines di tipo PH polinomiali e` stato studiato il metodo di Newton per una i distribuzione non uniforme dei nodi. Da ultimo la visita del Prof. Schaback a Milano, ha permesso di dimostrare quali siano i limiti di variazione di forma e scala delle funzioni a base radiale per mantenere la non singolarita` della matrice di interpolazione in R^d. Tale possibilita` e` particolarmente interessate per migliorare l’utilizzo di tali basi nella ricostruzione di funzioni da un campione di valori funzionali.

3 - Progetto: Sistemi di nuova concezione e applicazioni avanzate

Principali temi della ricerca: Elaborazione delle Immagini e Visione Computazionale, problemi di analisi di immagini, basi di dati, linguaggi visuali e interfacce uomo-macchina, sistemi informativi territoriali , tecniche di electronic ink , reflection computazionale, modelli prestazionali di sistemi distribuiti e paralleli

Nell’ambito dell’Elaborazione delle Immagini e della Visione Computazionale, l’attività di ricerca ha riguardato l'acquisizione automatica di modelli, la realtà virtuale, e l'image based rendering. Piu' in particolare, sono state studiate tecniche e metodologie per la realizzazione di interfacce uomo macchina, con applicazioni ai veicoli subacquei, ai veicoli spaziali ed all'ausilio ai non vedenti. In campo subacqueo, la ricerca è stata mirata a migliorare le prestazioni ed allargare l'applicabilità di veicoli subacquei teleguidati per l'ispezione e il controllo di installazioni subacqueee, mediante la definizione di tecniche per la sintesi automatica del modello tridimensionale della scena a partire dai dati sensori. Tecniche di sintesi sonora (sonificazione) sono state studiate al fine di aumentare con stimoli acustici la "normale" percezione visiva umana. Il ruolo della macchina consiste nell'analisi visiva della scena e nella sintesi di suoni legati alla struttura e al contenuto della scena. I risultati favoriranno il progetto di interfacce uomo-macchina piu efficaci dal punto di vista percettivo e/o la realizzazione di strumenti di ausilio ai non vedenti.

Inoltre la ricerca è stata indirizzata allo studio e allo sviluppo di metodi in grado di affrontare problemi di analisi di immagini di forte valenza applicativa mediante tecniche mutuate da recenti progressi nel campo della Teoria Statistica dell'Apprendimento. In particolare sono stati affrontati problemi inerenti la sorveglianza, il monitoraggio e la classificazione di eventi dinamici in scene di interni e lo sviluppo di un prototipo industriale di un sistema in grado di apprendere da esempi il peso di pesci di allevamento in tempo reale. E’ stato inoltre definito un metodo statisticamente robusto per confrontare due immagini e valutarne la somiglianza sotto condizioni piuttosto generali. L'obiettivo in questo caso e' la messa a punto di una funzione di somiglianza utilizzabile come "kernel" di support vector machine in grado di riconoscere oggetti in ambienti naturali da una sequenza di immagini in assenza di modelli espliciti 3D.

Nell'ambito delle basi di dati sono stati studiati problemi riguardanti lo sviluppo di strutture dati ed algoritmi efficienti per la ricerca esatta o approssimata su basi di dati di grandi dimensioni. In particolare nell'ambito delle basi di dati multimediali si è studiato il problema del "best-match" retrieval di immagini organizzando opportunamente le informazioni in una struttura dati "trie" in cui la ricerca è effettuata con operazioni efficienti di attraversamento e di potatura. Le operazioni di ricerca possono essere ottimizzate riducendo lo spazio di ricerca con una tecnica di clustering. E’ stato anche progetttato un modello di database Probabilistico che generalizza quello di Subrahmanian nel sistema Probview. Sono state inoltre introdotte tecniche di indicizzazione di immagini basate su relazioni spaziali, in un ambiente in cui sono integrate tecniche di elaborazione di immagini, applicazioni grafiche e di disegno, tecniche di indicizzazione basate su caratteristiche morfologiche e geometriche. Nell’ambito delle compressione di immagini sono stati definiti potenti schemi di codifica basati sulla combinazione degli algoritmi di Fisher e Saupe e sulla combinazione del centro di massa.

Nell’ambito dei linguaggi visuali e interfacce uomo-macchina sono stati progettati e realizzati potenti strumenti di generazione automatica di ambienti di programmazione visuale in grado di assistere il progettista nella definizione del linguaggio visuale di suo interesse. Tali generatori potranno costituire la base per la costruzione di potenti Meta-Case Workbenches, per la generazione automatica di interfacce grafiche e la prototipazione di applicazioni ipermediali e multimediali. E’ stata inoltre sviluppata una teoria formale dei linguaggi visuali per il dialogo utente-calcolatore che ha portato ad una interessante ed efficace metodologia di progetto di sistemi interattivi visuali. E’ continuato lo studio e lo sviluppo di tecniche per la valutazione dell'usabilita' di interfacce utente multimediali, in particolare una nuova tecnica è stata sviluppata e valutata con formali esperimenti controllati. E’ continuato inoltre il lavoro relativo agli aspetti formali della visualizzazione, interrogazione visuale di basi di dati, interfacce per WWW, e interfacce per biblioteche elettroniche.

Nel campo dei sistemi informativi territoriali (i cosiddetti GIS), i linguaggi di interazione uomo-computer rappresentano oggi un mezzo promettente per permettere ad utenti inesperti di interrogare database geografici. In questo ambito di ricerca è stato definito un ambiente visuale che è di ausilio alla manipolazione dei dati territoriali, tramite un’interfaccia grafica amichevole e un linguaggio visuale di interrogazione, il “Metaphor GIS Query Language” (MGISQL). Tale linguaggio si basa su una rappresentazione visuale dei dati, denominata geometafora, in grado di catturarne simultaneamente la componente topologica e quella tematica.

Nell’ambito dello sviluppo di tecniche di electronic ink per la scrittura di testi su Pocket PC palmari, sono state realizzate due versioni di un sistema interattivo basato su penna e touch screen per la scrittura rapida di testi su palmari privi di tastiera. Il primo metodo si chiama WordTree e usa una tecnica interattiva per selezionare parole da un dizionario rappresentato da una struttura ad albero. Il secondo metodo e` un raffinamento del primo basato su uno stack su cui compaiono in ordine decrescente di frequenza le parole piu usate del dizionario. Questo metodo e` progettato per applicazioni wireless mobili da usarsi in modalita` "location-aware".

Nell’ambito della reflection computazionale è stato sviluppato ed implementato in Java un middleware riflessivo il cui compito principale è quello di ovviare ad alcuni problemi tipici dei middleware classici:

- rendere facilmente estendibile e personalizzabile il meccanismo di comunicazione;

- svincolare l'applicazione dalla gestione delle comunicazioni (sincronizzazione, sicurezza e così via);

- considerare la comunicazione stessa come un cittadino di prima classe in grado di agire autonomamente su ogni suo singolo passo.

In particolare il framework realizzato apre il meccanismo adottato da Java per le invocazioni di metodi remoti.

E` inoltre in fase avanzata di sviluppo un linguaggio di programmazione chiamato IO che introduce i costrutti e le proprieta` della riflessione svincolandoli sia dalla metodologia object-oriented sia dai costrutti del linguaggio, ma basandola sull'implementazione del run-time system del linguaggio stesso.

Nell’ambito dello studio di modelli prestazionali di sistemi distribuiti e paralleli sono state investigate tecniche per ottenere informazione dettagliata sul comportamento di tali sistemi sia dal punto di vista quantitativo sia dal punto di vista qualitativo. In particolare è stata rivolta l’attenzione all’analisi di sistemi che non presentano un comportamento altamente simmetrico e per i quali i modelli di analisi proposti in letteratura soffrono di una perdita di informazione che rende impossibile provare alcune proprietà. A questo scopo sono state definite delle tecniche per costruire da tali modelli una catena di Markov “lumped” allo scopo di effettuare una efficace analisi della performance.

4 - Progetto: Matrici con struttura: analisi, algoritmi e applicazioni.

Principali temi della ricerca: Matrici di Toeplitz semi-infinite e bi-infinite con applicazioni; Operatori displacement; Disegno ed analisi di algoritmi per problemi di teoria delle code e equazioni matriciali; Problemi relativi a polinomi; Proprieta' spettrali e precondizionamento

Matrici di Toeplitz semi-infinite e bi-infinite con applicazioni. Sono stati individuati e analizzati nuovi metodi per il calcolo della fattorizzazione di Wiener-Hopf. Sono state considerate condizioni di esistenza della fattorizzazione di Wiener-Hopf per matrici multilivello.

Sono stati analizzati gli algoritmi di Krein, il ``band extension'', i metodi di proiezione e algoritmi basati sulla strategia divide et impera.

Sono stati analizzati e fra loro correlati i metodi di riduzione ciclica per matrici finite, semi-infinite e bi-infinite, e l'iterazione di Graeffe. Sono stati messi in relazione i problemi di fattorizzazione di Wiener-Hopf e di risoluzione di certe equazioni matriciali. Come risultato di questo studio

sono stati ottenuti algoritmi di costo $O(n\log^2n+n\log n\log\log\epsilon^{-1})$ per la fattorizzazione di matrici di Toeplitz a banda di ampiezza $n$ con errore $O(\epsilon)$. Algoritmi con analogo costo computazionale sono stati ottenuti per la fattorizzazione di polinomi di Laurent di grado $n$. Tali algoritmi sono stati estesi a serie di potenze. Sono stati analizzati casi di matrici perturbate.

Operatori displacement E stato introdotto il concetto di rango approssimato di dislocamento, ed e' tato applicato alla risoluzione di problemi di inversione di matrici di Toeplitz a elementi scalari e a blocchi con l'iterazione di Newton e con riduzione ciclica. I risultati sono stati applicati a problemi di restauro di immagini. Sono stati studiati metodi di risoluzione per sistemi bilivello di Toeplitz a banda.

Disegno ed analisi di algoritmi per problemi di teoria delle code e equazioni matriciali. Sono stati analizzate strutture a due livelli che intervengono in problemi della teoria delle code; in particolare strutture esterne Toeplitz e strutture interne di Frobenius. Sono state analizzate strutture definite per ricorsivit\`a di matrici semi-infinite ad albero ed individuati nuovi metodi di risoluzione per problemi associati. In particolare sono state considerate classi di equazioni matriciali associate a

queste strutture e proposti nuovi metodi di risoluzione. Sono state introdotte metodologie per trasformare sistemi di Hessenberg a blocchi in sistemi con matrice tridiagonale a blocchi. Sono stati analizzati gli algoritmi conseguenti. Sono stati trattati modelli di code del tipo PH/PH/1, QBD, M/G/1, G/M/1.

Problemi relativi a polinomi Sono stati individuati nuovi metodi per fattorizzare polinomi rispetto alla circonferenza unitaria e rispetto all'asse immaginario. Tali metodi sono stati estesi alla fattorizzazione rispetto a arbitrarie curve di Jordan nel piano complesso. Sono stati studiati problemi di stabilit\`a e di localizzazione di radici di polinomi.

Proprieta' spettrali e precondizionamento Sono state analizzate proprieta' spettrali asintotiche di classi di matrici con struttura, con particolare interesse allo studio del condizionamento asintotico e all'analisi di precondizionatori. E' stata introdotta una teoria unificante, basata sul teorema di Korovkin, per il precondizionamento in algebre trigonometriche di matrici di Toeplitz. Sono stati analizzati flussi isospettrali di matrici con struttura. Sono state fornite generalizzazioni di matrici di Toeplitz con l'introduzione del concetto di struttura ``localmente Toeplitz''. I risultati sono stati applicati al disegno di precondizionatori per operatori differenziali a coefficienti non costanti. Sono state analizzate strategie multigrid per la risoluzione di sistemi di Toeplitz. La teoria spettrale asintotica delle matrici strutturate e' stata applicata alla analisi asintotica della distribuzione degli zeri di polinomi ortogonali.

5 - Progetto: Metodi numerici per equazioni differenziali ordinarie e applicazioni.

Principali temi di ricerca: Equazioni differenziali su manifolds di matrici; Questioni di Algebra Lineare numerica legate alla derivazione ed implementazione di metodi alle differenze ; Analisi delle potenzialita’ riguardo allo sviluppo di nuovo software matematico; Derivazione ed analisi di metodi alle differenze per equazioni differenziali stocastiche; Metodi efficienti per equazioni integrali di Volterra e Metodi

Analisi e sviluppo di metodi stabili per equazioni differenziali con ritardo e relativo software.

Raggio spettrale di famiglie di matrici. Approssimazione di funzioni di matrici basata su polinomi di Faber.

Equazioni differenziali su manifolds di matrici con particolare riferimento ai gruppi di matrici quadratico. Il gruppo quadratico di Lorentz, noto nella letteratura della Fisica, e’ stato studiato proponendo metodi numerici per la risoluzione di equazioni differenziali ordinarie su questo gruppo. Sono stati studiati metodi numerici di tipo esplicito e semi esplicito che conservano la soluzione sulla manifold considerata. Sono state studiate anche le proprieta’ dei metodi numerici riguardo la conservazione della simmetria della soluzione. Il problema dell’interpolazione sulla manifold delle matrici ortogonali e’ stato anche affrontato proponendo un metodo che interpola sull’algebra associata alla manifold. E' stata affrontata anche la risoluzione di sistemi nonlineari sul gruppo quadratico, che vengono nell’applicazione di metodi numerici impliciti.

Questioni di Algebra Lineare numerica legate alla derivazione ed implementazione di metodi alle differenze per equazioni differenziali. In questo ambito si e' trattata la risolubilita’ dei problemi discreti generati dalla applicazione dei metodi numerici. L'analisi delle potenzialita’ riguardo allo sviluppo di nuovo software matematico. Tale analisi ha riguardato lo stato dell’arte riguardo ai codici di calcolo per la soluzione di equazioni differenziali. Derivazione ed analisi di metodi alle differenze per equazioni differenziali stocastiche. Questo aspetto della ricerca ha riguardato la derivazione di schemi predittore-correttore, basati su metodi tipo Adams, per equazioni differenziali stocastiche, con particolare riferimento alla formulazione di Stratonovich del problema .

Metodi efficienti per equazioni integrali di Volterra e Metodi numerici per equazioni differenziali ordinarie. Per quanto riguarda il primo punto, per equazioni con nucleo di convoluzione polinomiale lineare, sono stati sviluppati metodi fast fully paralleli. Per equazioni integrali a nucleo debolmente singolare, dei metodi sviluppati si è analizzata l'ordine e la convergenza rispetto alle iterazioni in funzione della singolarità e della costruzione della mesh di iterazione. Per lo studio della stabilità di metodi numerici per equazioni integrali di Volterra, sono state considerate classi di equazioni discrete di Volterra, sia di tipo convolutorio che non convolutorio, ed anche di tipo stocastico. Per la prima classe si sono determinate condizioni di limitatezza, di esponenziale stabilità e di periodicità della soluzione. Per le equazioni alle differenze stocastiche, si sono determinate condizioni sufficienti per la stabilità in probabilità della soluzione. Sono stati costruiti nuovi metodi Runge-Kutta-Nystrom esatti in fase o phase-fitted per Equazioni Differenziali Ordinarie con soluzioni oscillanti; questi metodi, producendo un errore di fase omogeneo che risulta nullo sull'equazione test lineare, sono idonei ad integrare sistemi lineari oppure ODEs nelle quali le oscillazioni di alta frequenza sono prodotte da una parte lineare. Si è dimostrato che per un metodo bdf a due passi il valore ottimo delle frequenze dipende non dal comportamento della soluzione, bensì dall'andamento di derivate di ordine elevato della soluzione stessa.

Sull' Analisi e sviluppo di metodi stabili per equazioni differenziali con ritardo e relativo software. si sono affrontati i seguenti temi: Approfondimento di metodi per le equazioni neutrali con ritardo proporzionale. Approfondimento delle problematiche relative alle equazioni con ritardo dipendente dallo stato. Sviluppo di metodi basati sulla formulazione in problema di Cauchy astratto e individuazione di algoritmi asintoticamente stabili. Sviluppo del codice RADAR5 per equazioni neutrali con ritardo "state dependent" basato sul metodo di RadauIIA.

Sul raggio spettrale di famiglie di matrici si è affrontato preliminarmente lo studio teorico di alcuni aspetti riguardanti il comportamento asintotico dei prodotti di matrici di famiglie limitate, con particolare riferimento all'ordine asintotico. Sotto opportune ipotesi per le famiglie di matrici, si sono poi sviluppati degli algoritmi per l'individuazione di norme politopiche estremali. Tali algoritmi sono stati applicati alle famiglie di matrici associate alle equazioni lineari alle differenze che scaturiscono dall'uso di metodi multistep lineari BDF con passo variabile per la risoluzione numerica di equazioni differenziali ordinarie. Si sono così migliorati alcuni risultati noti riguardanti la zero stabilità dei predetti metodi, trovando in effetti risultati ottimali.

Sull' approssimazione di funzioni di matrici basata su polinomi di Faber sono state affrontate approssimazioni di tipo polinomiale per funzioni di matrici utilizzando teorie tipiche dell'analisi nel campo complesso. In particolare sono stati messi a punto metodi numerici basati sull'uso dei polinomi di Faber di cui sono note le ottimali proprieta' di approssimazione. Le applicazioni di tali metodi nel contesto della soluzione di problemi differenziali hanno messo in evidenza la loro competitività nei confronti di altre metodologie proposte in letteratura.

6 - Progetto: Metodi iterativi per sistemi di equazioni non li­neari e problemi di ottimizzazione di dimensione finita -

Principali temi della ricerca: sviluppo e analisi di metodi per la risoluzione di sistemi non lineari di grandi dimensioni e relative applicazioni; sviluppo e analisi di metodi iterativi per la risoluzione di problemi di programmazione non lineare di grandi dimensioni e relative applicazioni; sviluppo e analisi di metodi per l'ottimizzazione globale; analisi di metodi di regolarizzazione per l'elaborazione di dati sperimentali.

Sviluppo e analisi di metodi per la risoluzione di sistemi non lineari di grandi dimensioni e relative applicazioni. Per la risoluzione di sistemi non lineari di grandi dimensioni è stata presa in esame la classe dei metodi di Newton Inesatti.

In particolare è stato sviluppato il metodo di Newton della Media Aritmetica per sistemi ove la matrice iacobiana è una matrice T(q,r), come nel caso di sistemi derivanti dalla discretizzazione di problemi ai limiti di tipo ellittico. L'idea di base di questo approccio consiste nel risolvere il sistema lineare interno al metodo di Newton mediante lo schema iterativo della Media aritmetica, usando un criterio di termine adattivo o, alternativamente, fissato a priori. Il metodo ha un alto grado di parallelismo intrinseco che determina notevole efficienza su architetture di tipo parallelo.Si e' sviluppata l'analisi di convergenza del metodo, con particolare riguardo al caso in cui una condizione di invarianza di Lipschitz vale per la matrice iacobiana. Speciale attenzione è riservata al caso dei sistemi debolmente non lineari, per cui viene approfondita l'analisi teorica di convergenza e viene effettuata una vasta sperimentazione numerica.

Un analogo approccio alla risoluzione di sistemi non lineari di grandi e' stato preso in esame; in questo caso i metodi di Newton e Quasi-Newton Inesatti sono combinati con un risolutore iterativo a blocchi di tipo row-action (Cimmino). Nel caso di una matrice iacobiana fortemente sparsa, un opportuno suo partizionamento in blocchi di righe mutuamente ortogonali permette di risolvere facilmente i sottoproblemi ai minimi quadrati introdotti dal solutore lineare. Gli schemi proposti sono intrinsecamente paralleli, essendo basati sulla soluzione indipendente di p sistemi sottodeterminati, p essendo il numero dei processori impiegati. La sperimentazione numerica del metodo è stata effettuata su CRAY-T3E, usando problemi test non lineari derivanti dalla discretizzazione di equazioni differenziali alle derivate parziali.

I metodi iterativi alla Newton sono stati applicati alla risoluzione di sistemi non lineari derivanti dalla discretizzazione di modelli di flusso multifase negli acquiferi. Nel problema del trasporto di contaminanti pesanti in mezzi porosi, il modello matematico è costituito da un'equazione di flusso nonlineare accoppiata, ancora in maniera nonlineare, ad un equazione di trasporto del contaminante.

Un metodo agli elementi finiti misti ibridi (MHFE) è stato utilizzato per la discretizzazione del problema di flusso, mentre l'equazione di trasporto è stata risolta tramite un metodo basato sulla tecnica di time-splitting, che combina il metodo MHFE per il termine dispersivo e lo schema ai volumi finiti ad alta risoluzione (FV) per il termine convettivo. Le nonlinearità vengono risolte tramite uno schema alla Picard, e la convergenza è assicurata tramite un controllo dinamico del passo temporale. Il vantaggio teorico di tale approccio, rispetto a tecniche agli elementi finiti o alle differenze finite convenzionali, è risultato evidente nei confronti effettuati sia per quanto riguarda l'accuratezza del campo di moto, sia per la stabilità dello schema in presenza di fronti ripidi. Il codice è stato poi utilizzato per la simulazione dell'infiltrazione di un contaminante pesante da un lago salato verso un acquifero, un problema fisico intrinsecamente instabile, che si manifesta con formazione di fingers.

Nella soluzione di problemi di diffusione con varie discretizzazioni spaziali è necessario il calcolo degli autovalori più piccoli di matrici simmetriche di grandi dimensioni. A tale scopo è stato analizzato l'algoritmo di Jacobi-Davidson combinato a precondizionatori quali Jacobi a blocchi, ILU(0) e AINV( basato sulla fattorizzazione incompleta dell'inversa della matrice dei coefficienti). La versione parallela del codice ha mostrato un alto livello di parallelismo sul CRAY T3E insieme ad un buon grado di scalabilità.

In collaborazione con il Dott. Sofroniou della Wolfram Research Inc., Champaign, Illinois, U.S.A., è stato sviluppato un "framework" per la soluzione numerica di equazioni differenziali ordinarie nell'ambito di Mathematica. Nel caso di non linearità, i procedimenti di soluzione coinvolgono l'iterazione di Newton e la costruzione, simbolica oppure approssimata (ad esempio agli elementi finiti) della matrice iacobiana.

Sviluppo e analisi di metodi iterativi per la risoluzione di problemi di programmazione non lineare di grandi dimensioni e relative applicazioni.

I codici attualmente disponibili per la risoluzione di problemi di programmazione lineare e quadratica vincolata mediante i metodi del punto interno (IP) usano risolutori interni diretti, perche' quelli iterativi sono considerati non competitivi.

Tuttavia esistono speciali classi di problemi di grandi dimensioni in cui la matrice dei vincoli ha una struttura adatta ad essere risolta su calcolatori paralleli (problemi derivanti dalla discretizzazione di problemi di controllo ottimo lineare-quadratico, problemi di distribuzione di risorse su rete, problemi di programmazione stocastica,…). Per tali problemi, si propone l'uso di un metodo IP combinato con un risolutore interno iterativo che usa una regola di terminazione adattiva, in modo da evitare iterazioni interne non necessarie quando si è lontani dalla soluzione. Usando i risultati sulla convergenza dei metodi di Newton inesatti, si stabilisce un criterio di arresto adattivo per un metodo IP combinato con un algoritmo di gradiente coniugato precondizionato e si prova la convergenza globale dello schema ottenuto, detto IPPCG. E' stato sviluppato un codice parallelo che implementa il metodo IPPCG su Cray T3E e SGI Origin 2000 per problemi di pianificazione di risorse in condizioni di incertezza, in cui la matrice dei vincoli presenta una struttura biangolare a blocchi. Per il metodo dei gradienti coniugati, è stato individuato un precondizionatore diagonale a blocchi, che è stato fattorizzato usando routine che rappresentano lo stato dell'arte nella risoluzione di matrici sparse definite positive (pacchetto di NG e Peyton). Gli esperimenti numerici mostrano una buona scalabilità del codice su Cray T3E. L'accuratezza dell'algoritmo proposto è paragonabile al ben noto codice seriale LOQO mentre gli speedup ottenuti rispetto al codice seriale su SGI Origin 2000 appaiono competitivi.

E' stata approfondita l'analisi dei metodi a proiezione variabile per la risoluzione di problemi di programmazione quadratica (QP) convessa, come quelli che si usano entro i metodi di approssimazione del costo (Patriksson, 2000) per la soluzione di generali problemi di ottimizzazione non lineare e di disequazioni variazionali. Entro tale schema iterativo (basato sulla risoluzione di una sequenza di sottoproblemi QP con gli stessi vincoli del problema originario, ricadono gli algoritmi classici di decomposizione, di proiezione e di proiezione modificata di Bertsekas. Assumendo di risolvere in modo inesatto i sottoproblemi interni allo schema iterativo (per esempio, riformulandoli come problemi di complementarità lineare mista e risolvendoli mediante metodi di decomposizione), sono state stabilite le condizioni che assicurano la convergenza sotto l'ipotesi di sola limitatezza della successione dei parametri di proiezione. L'efficacia dell'approccio proposto è stato valutato su problemi test con prefissate caratteristiche, presi anche dalla collezione CUTE.

Una applicazione di notevole interesse è stata sviluppata in collaborazione con il Prof. Verri del DISI di Genova nell'ambito della metodologia di classificazione binaria nota con il nome di Support Vector Machine (SVM). Tale metodologia consente di individuare la classe di appartenenza di un evento a partire da un certo numero di eventi per i quali la classe di appartenenza stessa risulti nota (apprendimento da esempi). L'idea alla base di una SVM consiste nella separazione degli eventi appartenenti a due classi diverse mediante una superficie che massimizzi la distanza dei punti più vicini alla superficie stessa. Dal punto di vista computazionale, l'implementazione della SVM richiede la risoluzione di un problema di programmazione quadratica (QP) con vincoli di tipo "box" ed un solo vincolo lineare di uguaglianza. Nel caso di superfici di decisione non lineari la matrice hessiana può assumere la forma speciale A=(a_ij)=(exp(-||z_i-z_j||^2/(2s²)) con z_i, z_j ÎR^m, sÎR . Essendo la dimensione del problema uguale al numero degli eventi utilizzati per addestrare la metodologia, in molte applicazioni di interesse pratico tale problema è di grandi dimensioni. Si è visto che i metodi iterativi a proiezione variabile sono adeguati a sfruttare la particolare natura della matrice A e convergono rapidamente anche quando il problema presenta bassi livelli di sparsità. Il metodo richiede la memorizzazione esplicita della matrice A e quindi non è applicabile nei casi in cui le dimensioni del problema sono così elevate (n >> 5000) da non rendere possibile tale memorizzazione. In queste situazioni il problema viene affrontato con opportune tecniche di decomposizione (Joachims T., 1998; Osuna E., Freund R., Girosi F., 1997) che richiedono la risoluzione di una sequenza di problemi QP di dimensione ridotta per i quali il metodo proposto risulta un efficiente risolutore. Il comportamento dello schema introdotto è stato valutato risolvendo alcuni noti problemi di classificazione binaria e mediante confronto con risolutori QP di libreria .

Sviluppo e analisi di metodi per l'ottimizzazione globale.

E' stata studiata una classe di nuovi metodi basati su una tecnica di partizionamento del dominio di ricerca dei punti di minimo globale. Si utilizza la norma uniforme della funzione obiettivo per selezionare progressivamente i subdomini in cui sono localizzati tali punti e ridurre la regione di ricerca. Usando una condizione di lipschitzianità della funzione obiettivo, si è dimostrato che il metodo proposto è globalmente convergente in probabilità.

Usando un approccio di tipo deterministico, in collaborazione con il Prof. Sergeyev, sono stati messi a punto nuovi algoritmi per la risoluzione di problemi in cui la funzione obiettivo è holderiana, utilizzando differenti tecniche a seconda che la costante di Holder sia nota a priori a sia incognita.

Analisi di metodi di regolarizzazione per l'elaborazione di dati sperimentali Nell'ambito della risoluzione di problemi inversi derivanti dalla discretizzazione di equazioni integrali di Fredholm di I specie si sono analizzati metodi di regolarizzazione per risolvere il problema dei minimi quadrati che si ottiene e che è fortemente mal posto. In particolare, si sono studiati due problemi applicativi:

la ricostruzione di un'immagine tomografica (a raggi X o per emissione), ottenuta discretizzando l'equazione integrale e risolvendo il sistema cosi' ottenuto con un metodo di tipo gradiente coniugato utilizzato come regolarizzatore. Si sono studiati opportuni criteri di arresto;

- la ricostruzione di una sequenza di immagini di Risonanza Magnetica dinamica, in cui il problema numerico è quello di risolvere un'equazione integrale con dati sottocampionati. L'approccio utilizzato è quello di approssimare la funzione soluzione con una combinazione lineare di funzioni esponenziali, i cui coefficienti sono calcolati risolvendo sistemi lineari con matrici di Toeplitz complesse hermitiane semidefinite positive. Si sono esaminati i metodi di regolarizzazione della TSVD (decomposizione in valori singolari troncata), Lavrent'yev e metodi iterativi.

7 - Progetto:Problemi di parturbazione singolare; Tecniche adattative di decomposizione dei domini

Partincipali temi della ricerca: Stime a posteriori e adattativita' per problemi a frontiera libera

e di evoluzione. Stime a posteriori per problemi di transizione di fase. Stime a posteriori ottimali per equazioni di evoluzione. Evoluzione geometrica di fronti: evoluzione cristallina. Evoluzione di fronti e problemi geometrici in Calcolo delle Variazioni. Metodi adattativi per l'evoluzione di fronti. Metodi di decomposizione di domini. Meccanica strutturale e magnetostatica.

Stime a posteriori e adattativita' per problemi a frontiera libera e di evoluzione. I metodi numerici adattativi per la risoluzione di equazioni alle derivate parziali consentono di concentrare lo sforzo computazionale dove richiesto dalla natura singolare della soluzione e/o del modello differenziale. Il conseguente risparmio di risorse computazionali consente di affrontare problemi di grandi dimensioni e di reale interesse applicativo come pure di aumentare cosiderevolmente l'accuratezza delle approssimazioni ottenute. La localizzazione del raffinamento del calcolo viene indicata dalle cosiddette stime a posteriori locali dell'errore. Si tratta di stime dell'errore espresse in termini di quantita' calcolabili effettivamente durante l'esecuzione dell'algorimo di approssimazione. Gli indicatori devono essere locali, semplici da calcolare, convergenti e possibilmente efficaci. I problemi a frontiera libera e i problemi di evoluzione degeneri sono tra quelli che possono trarre un beneficio maggiore da una risoluzione adattativa.

Stime a posteriori per problemi di transizione di fase. Sono state dimostrate stime a posteriori locali per problemi tipo Stefan. La dimostrazione si basa sulla nota tecnica del problema duale, applicata qui per la prima volta in modo rigoroso nel contesto di problemi singolari. \`E stata anche affrontata l'implementazione efficiente di un algoritmo di elementi finiti lineari adattativo basato sulle stime a posteriori introdotte. Le operazioni di raffinamento locale e di deraffinamento delle reticolazioni vengono eseguite con la tecnica di bisezione, estremamente veloce e di semplice implementazione sia nel caso bidimensionale che in quello tridimensionale.

Stime a posteriori ottimali per equazioni di evoluzione. Si e' considerata un'ampia classe di equazioni di evoluzione in uno spazio di Hilbert (con un operatore che fosse il sottodifferenziale di una funzione convessa semicontinua inferiormente); in questa classe rientrano problemi fortemente non lineari di carattere degenere oppure singolare di interesse applicativo,quali modelli di transizione di fase, equazioni quasi-lineari, equazioni di reazione-diffusione. Considerando la piu' semplice approssimazione temporale, il metodo di Eulero implicito, sono stati introdotti nuovi estimatori a posteriori dell'errore, utilizzando solamente la convessit\`a dell'operatore. Gli estimatori dipendono solamente dalla soluzione calcolata e dai dati e non richiedono alcun legame tra passi temporali consecutivi. Un altro importante risultato conseguito \`e la convergenza di tali estimatori con una velocit\`a ottimale rispetto alla regolarit\`a della soluzione.

Evoluzione geometrica di fronti: evoluzione cristallina. La ricerca si \`e focalizzata sullo studio dell'evoluzione per curvatura media cristallina di superfici nello spazio. La simulazione numerica \`e stata affrontata tramite una preliminare regolarizzazione della legge di evoluzione con una equazione parabolica di reazione-diffusione singolarmente perturbata (equazione di Allen-Cahn). L'approccio proposto produce una simulazione corretta anche in situazioni particolari, comprendenti il cosiddetto fenomeno di incurvamento delle facce, importanti nelle applicazioni. Vengono adottate strategie di localizzazione del calcolo alla sola regione di transizione, piccola rispetto all'intero dominio di lavoro. Si descrive il fenomeno di incurvamento e si cerca di rispondere in modo completo alla questione della ``calibrabilit\`a" di una faccia (quando cio\`e una faccia della superficie in evoluzione \`e destinata a traslare rigidamente oppure dovr\`a spezzarsi o incurvarsi).

Evoluzione di fronti e problemi geometrici in Calcolo delle Variazioni. L'evoluzione viene approssimata con una disequazione di reazione-diffusione a doppio ostacolo, singolarmente perturbata, con un opportuno termine tipo campo di fase insensibile alla scelta del potenziale. Sono state dimostrate stime ottimali per l'errore delle interfacce, nel caso di evoluzioni regolari, come pure stime lineari anche dopo la comparsa di singolarit\`a. L'algoritmo di approssimazione e' stato implementato nel caso bidimensionale e per flussi a simmetria assiale.

Metodi adattativi per l'evoluzione di fronti. Il cosiddetto problema di curvatura prescritta, definito in termini della minimizzazione di un funzionale di area nello spazio delle funzioni caratteristiche a variazione limitata, puo' essere regolarizzato e quindi formulato attraverso una disequazione variazionale. Sono state ottenute stime a posteriori dell'errore di discretizzazione per elementi finiti lineari. Su tali stime \`e basato un algoritmo adattativo. La novit\`a dei risultati ottenuti risiede nella presenza di pesi appropriati negli indicatori locali dell'errore. La soluzione del problema affrontato costituisce il passo temporale di un algoritmo di avanzamento implicito per l'evoluzione di fronti (via minimizzazione dell'energia superficiale e della funzione distanza), che pu\`o anche descrivere fenomeni di nucleazione e processi di analisi di immagini.

Stime dell'errore a priori, ottimali rispetto all'approssimazione con un problema variazionale di tipo doppio ostacolo sono state dimostrate anche per lo schema completamente discretizzato. Problemi di transizione di fase hanno rilevanza anche nell'ambito del riconoscimento di immagini. La minimizzazione del funzionale di Mumford e Shah \`e una delle tecniche recentemente proposte in questo campo, ma risulta estremamente oneroso dal punto di vista computazionale, si propongono alcune tecniche efficaci per la sua minimizzazione numerica.

Metodi di decomposizione di domini. Sono stati sviluppati e studiati metodi di decomposizione di domini per i sistemi di Stokes e dell'elasticit\`a lineare in due e tre dimensioni. Sono state considerate discretizzazioni sia ad elementi finiti che ad elementi spettrali e sia metodi di Schwarz con sovrapposizione che metodi di iterazione per sottostrutture senza sovrapposizione. In particolare \`e stata studiata la velocit\`a di convergenza dei metodi iterativi precondizionati risultanti, sia dal punto di vista teorico che numerico. Le stime di convergenza ottenute sono indipendenti dal numero di sottodomini e dipendono solo polilogaritmicamente dai parametri di discretizzazione spaziale e dal grado spettrale. Sono anche stati studiati metodi iterativi precondizionati per discretizzazioni spettrali dell'equazione di Helmholtz con condizioni al bordo di Sommerfeld. Sono stati proposti e studiati metodi di decomposizione di domini senza sovrapposizione per problemi di elettromagnetismo governati dalle equazioni di Maxwell, sia in regime armonico in tempo nel caso a bassa frequenza che in regime ad alta frequenza. Sono stati studiati metodi di decomposizione di domini di tipo Neumann-Neumann per problemi di diffusione-trasporto a trasporto dominante. Di questi metodi \`e stata effettuata l'analisi di convergenza che ha consentito l'individuazione del parametro ottimale di rilassamento sulle interfacce. E' stato condotto inoltre un confronto sperimentale su alcuni casi test di interesse realistico con il classico metodo di Neumann-Neumann, evidenziando la superiorit\`a dei metodi proposti nella maggioranza dei casi. E' stato studiato l'accoppiamento eterogeneo delle equazioni di Navier-Stokes per fluidi incomprimibili viscosi con le equazioni di Oseen e di Stokes in geometrie bidimensionali. Sono state proposte e studiate opportune condizioni di interfaccia che garantiscano una buona posizione del problema globale. E' stata realizzata un'approssimazione con elementi spettrali stabilizzati del problema eterogeneo e sono stati ottenuti risultati numerici avvaloranti la teoria studiata.

Meccanica strutturale e magnetostatica. Si sono individuate condizioni astratte per la convergenza di schemi agli elementi finiti misti per l'approssimazione di problemi agli autovalori

originati da sistemi di equazioni alle derivate parziali. Si \`e quindi utilizzata la teoria astratta per dimostrare che gli elementi finiti di tipo ``edge" forniscono approssimazioni ottimali dei cosidetti autovalori di Maxwell (problema della cavit\`a risonante). Si \`e altres\`{\i} considerata l'approssimazione mediante elementi finiti di tipo nodale del medesimo problema, osservando che tale metodo d\`a risultati del tutto inaffidabili. Sono possibili alcuni rimedi, che devono comunque essere usati con estrema cautela.

Per eventuali problemi contattare webmaster@altamatematica.it