Universita' degli Studi di PADOVA Progetti di Ricerca di Ateneo
Anno: 2008 - prot. CPDA089040
PARTE I
1.0 Macroarea di Afferenza del Responsabile Scientifico del Programma di Ricerca
1 - Matematica, scienze fisiche, dell'informazione e della comunicazione, ingegneria e scienze della Terra
1.1 Area Scientifica del Responsabile Scientifico del Programma di Ricerca
01 - Scienze Matematiche
1.2 Responsabile Scientifico del Programma di Ricerca
REDIVO ZAGLIA Michela F
(Cognome) (Nome) (sesso)
PROFESSORE ASSOCIATO MAT/08 19/04/1953
(Qualifica) (Settore Scientifico Disciplinare) (Data di Nascita)
RDVMHL53D59G224C Facoltà di INGEGNERIA DIP. MATEMATICA PURA E APPLICATA
(Codice di identificazione personale) (Facoltà) (Dipartimento/Istituto)
0498271378 0498271392 Michela.RedivoZaglia@unipd.it
(Prefisso e Telefono) (Numero Fax) (Indirizzo di Posta Elettronica)
1.3 Area Scientifica del Programma di Ricerca
nº
1. Area Scientifica Prevalente 01 Scienze Matematiche 100%
2. Area Scientifica -
3. Area Scientifica -
4. Progetto Interarea NO
1.4 Titolo del Programma di Ricerca Lingua Italiana
Interpolazione ed Estrapolazione: nuovi algoritmi ed applicazioni
Lingua Inglese
Interpolation and Extrapolation: new algorithms and applications
1.5 Abstract del Programma di Ricerca
Lingua Italiana
Questo progetto riguarda due argomenti importanti dell'approssimazione numerica, l'interpolazione polinomiale (caso multivariato), e i metodi di estrapolazione (con applicazioni all'algebra lineare numerica). Il gruppo di ricerca ha già basi solide e buone prospettive, in particolare nell'ottica della produzione di software numerico, e beneficerà di una rete consolidata di collaborazioni nazionali e internazionali (L. Bos (Calgary), C. Brezinski (Lille), Y. Xu (Eugene)) e potrà interagire fortemente grazie ai legami esistenti tra le due tematiche.
1) Interpolazione polinomiale multivariata
Si tratta di un campo di ricerca sostanzialmente aperto [e]. Un punto di svolta è stato fornito dai cosiddetti "punti di Padova" nel quadrato, che sono il primo esempio noto di punti unisolventi 2d la cui costante di Lebesgue abbia ordine di crescita minimale O(log^2(n)) [a,f]. Un'altra direzione è data dal calcolo di "punti approssimati di Fekete" a partire da matrici di Vandermonde tramite fattorizzazioni QR [b,h] (evitando così problemi di ottimizzazione nonlineare su larga scala).
Un approccio alternativo è l'iperinterpolazione, cioè sviluppi di Fourier in serie di polinomi ortogonali discretizzati con formule di cubatura algebriche di grado elevato [g].
Le direzioni principali in questo progetto sono:
- cercare di estendere la costruzione geometrica dei punti di Padova ad altri domini multivariati;
- sviluppare il metodo dei "punti approssimati di Fekete" nel caso reale (interpolazione, cubatura e collocazione multivariata su geometrie arbitrarie) e nel caso complesso (calcolo di equilibri piani discreti, di filtri polinomiali per l'elaborazione di segnali e sistemi mal condizionati, di funzioni di matrice);
- estendere ed implementare in modo efficiente l'iperinterpolazione in dimensione maggiore di 2, anche con produzione di software.
2) Metodi di estrapolazione: strumenti e applicazioni
In numerosi ambiti scientifici si presentano successioni e serie che convergono in modo così lento, da costituire un serio svantaggio per il loro utilizzo.
I metodi di estrapolazione sono alla base di nuovi metodi per la soluzione di tali problemi e di altri collegati (per una panoramica, si veda [c]).
Di particolare interesse sono i nuovi metodi di estrapolazione per successioni vettoriali. Per essi bisogna ottenere algoritmi ricorsivi che vanno programmati con estrema cura. Si devono anche cercare risultati teorici sulla convergenza e l'accelerazione, non così facili da ottenere, nonchè generalizzazioni di strumenti di algebra lineare (complementi di Schur, identità determinantali, ...).
Si studieranno con particolare attenzione due applicazioni principali:
- accelerazione di metodi iterativi per il calcolo di autovettori di matrici stocastiche riducibili (in particolare il PageRank di Google): il processo è molto lento e una della possibilità per accelerarlo è l'utilizzo di metodi di estrapolazione [1,2], anche su computer paralleli;
- individuazione, studio e test delle soluzioni regolarizzate di sistemi lineari mal condizionati nel caso multiparametrico [d], che hanno applicazioni in numerosi ambiti (image restoration, medical imaging, ...).
Bibliografia (si veda la versione inglese ed anche le pubblicazioni del Responsabile scientifico)
Lingua Inglese
This project concerns two important topics of numerical approximation, polynomial interpolation (in the multivariate setting), and extrapolation methods (with applications to numerical linear algebra). The research group has a sound basis and good perspectives, in particular towards the production of numerical software, and will benefit of a consolidate net of national and international collaborations (L. Bos (Calgary), C. Brezinski (Lille), Y. Xu (Eugene)) and will well interact thanks to the common link between the two lines of research.
1) Multivariate polynomial interpolation
This is a substantially open research field [e]. A turning point was given by the "Padua points" in the square, the first known example of unisolvent 2d points whose Lebesgue constant has minimal order of growth O(log^2(n)) [a,f]. Another direction is the computation of
"approximate Fekete points" from Vandermonde matrices by QR factorizations [b,h] (so avoiding large scale nonlinear optimization). An alternative approach is hyperinterpolation, that is discretized Fourier expansions in orthogonal polynomials via high-degree algebraic cubature [g].
The main directions in this project are:
- trying to extend the geometric construction of the Padua points to other domains;
- developing the method of "approximate Fekete points" in the real case (multivariate interpolation, cubature and collocation over arbitrary geometries) and in the complex case (computation of discrete planar equilibria, of polynomial filters for signal processing and ill-conditioned linear systems, of matrix functions);
- extending and implementing efficiently hyperinterpolation in higher dimensions.
2) Extrapolation methods: tools and applications
In several scientific domains, one has often to deal with sequences and series, that converge slowly and it is a serious drawback to their effective use.
Extrapolation methods form the basis of new methods for solving such and more problems (see [c]). Particular attention has to be given in obtaining new extrapolation methods for vector sequences. Recursive algorithms have to be obtained, and programmed with great care. We have also to look for theoretical results on convergence and acceleration as well as generalizations of Linear Algebra tools (Schur complements, determinant identities, ...), not so easy to obtain.
We plan to concentrate on two main applications:
- acceleration of iterative methods for the computation of eigenvectors of reducible stochastic matrices (in particular, Google PageRank): the process is very slow and one possibility for accelerating it, is to use extrapolation methods [1,2], also on parallel computers;
- study and test the regularized solutions of ill-conditioned linear systems in the multiparameter case [d], with applications to several domains (image restoration, medical imaging, ...).
References (see also the publications of the Principal Investigator):
[a] L.Bos, M.Caliari, S.De Marchi, M.Vianello, Y.Xu, Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J.
Approx. Theory 143 (2006).
[b] L.Bos, N.Levenberg, On the Approximate Calculation of Fekete Points: the Univariate Case, submitted.
[c] C.Brezinski, M.Redivo Zaglia, Extrapolation Methods. Theory and Practice, North-Holland, 1991.
[d] C.Brezinski, M.Redivo Zaglia, G.Rodriguez, G.Seatzu, Multi-parameter regularization techniques for ill-conditioned linear systems, Numer.
Math. 94 (2003).
[e] C.de Boor, Issues in multivariate polynomial interpolation, plenary talk at "Stanford 50", 3/2007.
[f] M.Caliari, S.De Marchi, M.Vianello, Algorithm 886: Padua2D: Bivariate Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software 35-3 (2008).
[g] S.De Marchi, M.Vianello, Y.Xu, New cubature formulae and hyperinterpolation in three variables, submitted.
[h] A.Sommariva, M.Vianello, Computing approximate Fekete poinys by QR factorizations of Vandermonde matrices, submitted.
1.6 Caratteri di innovatività del progetto e del gruppo
Lingua Italiana
Sin dagli anni '90, la responsabile di questo progetto e M. Vianello (un suo componente) hanno iniziato e mantenuto indipendentemente una collaborazione scientifica con gli altri partecipanti. A seguito di tali collaborazioni, essi hanno pubblicato diversi libri e articoli come coautori, collaborando intensivamente anche con visite e seminari nelle rispettive Università.
Nel 2005 l’Università di Padova ha stabilito un “Comitato di Valutazione” per valutare il Dipartimento di Matematica Pura ed Applicata. Nel suo report, tra altri commenti, il Comitato “ha ritenuto il frazionamento dei programmi altamente arbitrario o discutibile in qualche caso, specialmente nel casi di gruppi molto piccoli (talvolta composti da un'unica persona)”. E inoltre "... sembra che in qualche modo ci sia una spiacevole tendenza ad isolare in compartimenti differenti argomenti e risorse ... ".
Pertanto, pur avendo ottenuto per i loro programmi separati una buona valutazione, recependo la critica, i due ricercatori sopra citati hanno cercato di costruire un progetto in comune per collaborare assieme e trarre vantaggio dall'esperienza e dalle conoscenze dei loro due piccoli gruppi che avevano tematiche comuni.
L’innovatività prevalente contenuta in questo progetto è duplice: creare un gruppo di ricerca stabile con un programma a lungo termine su algoritmi avanzati di approssimazione, riunendo giovani ricercatori che già lavorano separatamente presso il Dip. di Matematica Pura ed Applicata dell’Università di Padova ed in altri Dipartimenti italiani; rafforzare una rete nazionale ed internazionale di ricerca attraverso collaborazioni anche con esperti stranieri su alcuni importanti argomenti dell'approssimazione numerica, con un particolare impegno nello sviluppo di software numerico efficiente e robusto.
Proprio in tale ottica, il progetto prevede la richiesta di una borsa di studio annuale per un giovane ricercatore, orientata allo sviluppo ed all'ottimizzazione di algoritmi e di sofware.
A sottolineare come l'interesse ed il desiderio di rafforzare l'unione dei due gruppi e l'internazionalizzazione sia ritenuta uno dei punti prevalenti, nel settembre del 2006 il responsabile del progetto e gli altri partecipanti italiani hanno organizzato un incontro internazionale (First Dolomites Workshop on Constructive Approximation Theory and Applications) a Canazei (TN, Italy), le cui tematiche scientifiche erano legate a quelle di questo progetto, che ha visto 85 partecipanti (da 5 continenti e 23 diverse nazioni), 14 invited speakers e 40 contributed talks (si veda http://profs.sci.univr.it/~dwcaa06/).
Anche quest'anno, per questo progetto, si è avuta l'adesione di eminenti esperti internazionali. Citiamo per essi due libri molto noti e particolarmente legati alle tematiche del progetto:
- Prof. C. Brezinski:
"Extrapolation Methods. Theory and Practice", North-Holland, 1991 (with M. Redivo-Zaglia).
- Prof. Y. Xu:
"Orthogonal Polynomials of Several Variables", Encyclopedia of Mathematics and its Applications 81, Cambridge University Press, 2001 (with
Charles F. Dunkl).
Lingua Inglese
The responsible for this project and Prof. M. Vianello, one of the members of the project, began already in the early '90s but independently, a scientific collaboration with the others participants to the project. These collaborations, accompanied with mutual visits and seminars among the involved Universities, gave rise to several papers and books.
In 2005 the University of Padova established an Evaluation Committee for evaluating the research activity of the Department of Pure and Applied Mathematics. In its report, the Committee said: “The Committee found that the division of research programmes was highly arbitrary or, in some occasion, disputable, especially in the case of very small groups (sometimes composed just by one person).” Moreover, “...it does seem that there is a regrettable tendency to isolate in compartments, topics and resources...”.
Hence, the above mentioned researchers, even if they obtained a good evaluation for their respective research proposals, by taking into account that criticism, have decided to propose a project for a common collaboration that will take advantage of their own research groups, experience and knowledge.
The novelty of this proposal is twofold. Firstly, it aims to create a stable research group with a long term program in advanced approximation algorithms, collecting young researchers already working separately at the Department of Pure and Applied Mathematics of Padua University and in other Italian Departments. Secondly, it aims to consolidate an international research net through collaborations with the foreign experts on some important aspects of numerical approximation. A special effort will be devoted to the development of efficient and robust numerical software.
Precisely, in this perspective, in the project we asked for an annual research grant for a young researcher, devoted to the development and to the optimization of algorithms and software.
To emphasize the interest of the research groups to collaborate and the internationality of their research, in September 2006 the responsible of the proposal with the other Italian participants, organized an international workshop (First Dolomites Workshop on Constructive Approximation Theory and Application) in Canazei (TN, Italy) with main topics related to the fields of interest of this new proposal. There were 85 participants from 5 continents, 23 different nations, 15 invited talks, 40 contributed talks and a poster session (see also http://profs.sci.univr.it/~dwcaa06/).
Also for this new proposal we have the participation of well-known researchers in Numerical Analysis and well recognized experts in the fields of research covered by this project. Here, we recall two well-known contributions to the scientific community of these researchers:
- Prof. C. Brezinski :
"Extrapolation Methods. Theory and Practice", North-Holland, 1991 (with M. Redivo-Zaglia).
- Prof. Y. Xu:
"Orthogonal Polynomials of Several Variables", Encyclopedia of Mathematics and its Applications 81, Cambridge University Press, 2001 (with Charles F. Dunkl).
1.7 Settori scientifico-disciplinari interessati dal Programma di Ricerca
MAT/08 ANALISI NUMERICA
1.8 Parole chiave
1.AREA 01 - Mathematics - Numerical Analysis - Numerical Approximation And Computational Geometry (Primarily Algorithms) - INTERPOLATION
2.AREA 01 - Mathematics - Numerical Analysis - Acceleration Of Convergence - EXTRAPOLATION TO THE LIMIT, DEFERRED CORRECTIONS
3.AREA 01 - Mathematics - Numerical Analysis - Numerical Linear Algebra - ILL-POSEDNESS, REGULARIZATION 4.Numerical Analysis - ALGORITHMS AND SOFWARE FOR INTERPOLATION AND EXTRAPOLATION
1.9 Curriculum scientifico del Responsabile Scientifico del programma di ricerca Lingua Italiana
MICHELA REDIVO ZAGLIA è professore associato di Analisi Numerica (SSD MAT/08) dal 1998. Ha svolto il suo servizio presso il
Dipartimento di Matematica dell’Università della Calabria dal 1998 al 2002 e successivamente presso il Dipartimento di Matematica Pura ed Applicata dell’Università di Padova. Ha diretto il Centro di Calcolo del Dipartimento di Elettronica ed Informatica dell’Università di Padova dal 1984 al 1998. E’ stata invitata in qualità di professore visitatore in numerose Università europee ed anche in Africa (Johannesburg e Marrakech) effettuando in tali occasioni più di 30 seminari sui suoi risultati scientifici. I suoi lavori sono stati presentati in circa 50 conferenze internazionali.
E’ stato membro di comitati di organizzazione e scientifici di 13 conferenze internazionali e nazionali ed ha collaborato, in qualità di editor, alla predisposizione di 7 proceedings pubblicati come uscite speciali di riviste internazionali. Ha partecipato, anche in qualità di conferenziere
invitato, a numerose conferenze internazionali relative alle sue aree di ricerca.
E’ membro del comitato di redazione di tre riviste internazionali di analisi numerica e matematica applicata (International Journal of Applied Mathematics and Engineering Sciences, Journal of Applied Mathematics e Numerical Algorithms). Per quest’ultima rivista ricopre anche, dal 1991, la qualifica di Software Editor. E’ stata inoltre membro di commissioni di dottorato in Italia, Francia, Portogallo e Marocco ed è membro del Collegio della Scuola di Dottorato di Ricerca in Scienze Matematiche (indirizzo di Matematica Computazionale) dell’Università di Padova.
Relativamente alla sua attività didattica, ha tenuto e tiene corsi di analisi numerica e di informatica negli ordinamenti relativi alla Laurea, al Master ed al Dottorato di Ricerca.
I suoi principali temi di ricerca riguardano l’analisi numerica. Essi coinvolgono differenti argomenti che sono comunque legati tra loro: metodi di estrapolazione ed accelerazione della convergenza, polinomi ortogonali classici e formali, e risoluzione di sistemi di equazioni. E’, in particolare, un’esperta internazionale nei metodi di estrapolazione, con applicazioni di tali metodi anche alla regolarizzazione di sistemi mal condizionati ed all'accelerazione dell'algoritmo di calcolo del PageRank utilizzato dal motore di ricerca Google. Ha ottenuto numerosi risultati nel trattamento del breakdown e del near-breakdown negli algoritmi che implementano il metodo di Lanczos ed i metodi correlati (CGS e BiCGSTAB) per la risoluzione di sistemi di equazioni lineari, facendo uso dei FOP (Formal Orthogonal Polynomials), ed anche risultati sui polinomi quasi-ortogonali, la loro misura di ortogonalità e la localizzazione dei relativi zeri.
Nell'ambito dei contatti di ricerca sta realizzando, in collaborazione con altri colleghi, un toolbox Matlab che racchiuda i metodi di base per il trattamento ottimizzato della matrici strutturate.
Come autore o coautore ha pubblicato circa 60 lavori su riviste internazionali e proceedings di conferenze e sei libri (uno dei quali in inglese, pubblicato nel 1991 da North-Holland, e due in francese, pubblicati nel 2004 e nel 2006 da Ellipses, Paris). Un altro libro è in preparazione.
Lingua Inglese
MICHELA REDIVO ZAGLIA is Associate Professor of Numerical Analysis since 1998. From 1998 to 2002, she was in the Department of Mathematics of Calabria University and after she moved to the Department of Pure and Applied Mathematics of the University of Padova. She has been Head of the Computer Center of the Department of Electronics and Computer Sciences of the University of Padova from 1984 to 1998. She has been Visiting Professor in several European Universities and also in Africa (Johannesburg and Marrakech) giving there more that 30 seminars on her scientific results. Her scientific works has been presented at about 50 international conferences.
She has been member of the Scientific and Organizing Committee of 13 Italian and International Conferences and has collaborated to the editing of 7 conference proceedings published as special issues of numerical analysis international journals. She attended, also as invited speaker, to several international conferences related to its areas of research.
She is member of the editorial board of three international journals of numerical analysis and applied mathematics (International Journal of Applied Mathematics and Engineering Sciences, Journal of Applied Mathematics, and Numerical Algorithms). For the last one she is also the software editor since 1991. She has been also member of Ph.D. examination committees in Italy, France, Portugal and Morocco and she is member of the board of the Doctoral School in Mathematics (Computational Mathematics) at University of Padova.
With regards on her teaching activities, she gave courses on numerical analysis and computer sciences for Laurea, Master and PhD degrees.
Her main scientific interests concern numerical analysis. They deal, in particular, with several topics which have some connections:
extrapolation methods and convergence acceleration, classical and formal orthogonal polynomials and solution of systems of equations. In particular, she is an international expert on extrapolation methods, with applications of such methods also to the regularization of
ill-conditioned systems and to the acceleration of the PageRank algorithm used in the Google's web search. She obtained several results in the treatment of breakdowns and near-breakdowns in algorithms for the implementation of Lanczos method and related methods (CGS and BiCGSTAB) for the solution of systems of linear equations, by using the FOP (Formal Orthogonal Polynomials), and also on quasi-orthogonal polynomials, their measure of orthogonality, and the location of their zeros.
A Matlab toolbox containing several methods for operating in an optimal way with stuctured matrices is under construction, in collaboration with other colleagues belonging to a common research project.
As author or coauthor she published about 60 papers in international journals and conference proceedings and five books (one of which in English, published in 1991 by North-Holland, and two in French, published in 2004 and in 2006 by Ellipses, Paris). Another book is in preparation.
1.10 Pubblicazioni scientifiche più significative del Responsabile Scientifico del Programma di Ricerca
nº Anno Tipo di Pubblicazione
Pubblicazione 1.2008 Articolo su
rivista
BREZINSKI C; REDIVO ZAGLIA M. (2008). Rational extrapolation for the PageRank vector.
MATHEMATICS OF COMPUTATION, vol. 77; p. 1585-1598, ISSN: 0025-5718, doi:
10.1090/S0025-5718-08-02086-3 (Articolo su rivista) impact factor: 1.155 2.2006 Articolo su
rivista
BREZINSKI C; REDIVO ZAGLIA M. (2006). The PageRank vector: properties, computation, approximation, and acceleration. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, vol. 28; p. 551-575, ISSN: 0895-4798 (Articolo su rivista) impact factor: 1.798
3.2005 Articolo su rivista
BREZINSKI C.; REDIVO ZAGLIA M.; SERRA-CAPIZZANO S. (2005). Extrapolation methods for Pagerank computations. COMPTES RENDUS MATHEMATIQUE, vol. 340; p. 393-397, ISSN: 1631-073X (Articolo su rivista) impact factor: .469
4.2007 Articolo su rivista
BREZINSKI C; REDIVO ZAGLIA M. (2007). Generalizations of Aitken's process for accelerating the convergence of sequences. COMPUTATIONAL AND APPLIED MATHEMATICS, vol. 26; p. 1-19, ISSN:
0101-8205 (Articolo su rivista) 5.2008 Articolo su
rivista
BREZINSKI C; REDIVO ZAGLIA M. (2008). Le classement des pages du web par les moteurs de recherche.
MATAPLI, vol. 85; p. 47-57, ISSN: 0762-5707 (Articolo su rivista) - février 2008
1.11 Modulo Riepilogativo Progetto
Costo complessivo del Programma di Ricerca 50.000
Il programma prevede assegni di ricerca per un importo totale di 0
Il programma prevede Attrezzature Scientifiche > di 5.000 euro per un importo totale di 0
1.12 Componenti il Gruppo di Ricerca
1.12.0 Personale docente e ricercatore dell'Università di Padova
nº Cognome Nome Dipartimento/Istituto Qualifica Settore Mesi/Persona(*) Primo anno
Mesi/Persona(*) Secondo anno
Adesione
1.REDIVO ZAGLIA Michela DIP.
MATEMATICA PURA E APPLICATA
Prof.
Associato
MAT/08 8 8 RESPONSABILE
2.SOMMARIVA Alvise DIP.
MATEMATICA PURA E APPLICATA
Ricercatore MAT/08 8 8 ACCETTATO
3.VIANELLO Marco DIP.
MATEMATICA PURA E APPLICATA
Prof.
Associato
MAT/08 8 8 ACCETTATO
1.12.1 Altro Personale dell'Università di Padova
nº Nome Dipartimento/Istituto Facoltà Qualifica Mesi/Persona(*)
Primo anno
Mesi/Persona(*) Secondo anno
1.12.2 Personale di Ruolo - dirigente medico e dirigente sanitario - delle Aziende Ospedaliere e Socio Sanitarie convenzionate con l'Università di Padova che operi nelle strutture universitarie e che vi svolga attività di ricerca
nº Cognome Nome Dipartimento/Istituto Qualifica Mesi/Persona(*)
Primo anno
Mesi/Persona(*) Secondo anno
1.12.3 Personale universitario di altre Università
nº Cognome Nome Università Dipartimento/Istituto Qualifica Settore Mesi/Persona(*) Primo anno
Mesi/Persona(*) Secondo anno 1.DE MARCHI Stefano Università degli
Studi di VERONA
DIP.
INFORMATICA
PROF.ASSOCIATO MAT/08 6 6
2.RODRIGUEZ Giuseppe Università degli Studi di CAGLIARI
DIP.
MATEMATICA
PROF.ASSOCIATO MAT/08 4 4
3.CALIARI Marco Università degli Studi di VERONA
DIP.
INFORMATICA
RIC.UNIVERSITARIO MAT/08 6 6
4.DELL'ACCIO Francesco Università della CALABRIA
DIP.
MATEMATICA
RIC.UNIVERSITARIO MAT/08 4 4
1.12.4 Titolari di assegni di ricerca dell'Università di Padova
nº Cognome Nome Dipartimento/Istituto Mesi/Persona(*)
Primo anno
Mesi/Persona(*) Secondo anno
1.12.5 Studenti di Dottorato di Ricerca, titolari di borse post-dottorato e iscritti alle scuole di specializzazione dell'Università di Padova (L. 398/89 art.4)
nº Cognome Nome Dipartimento/Istituto Qualifica Mesi/Persona(*)
Primo anno
Mesi/Persona(*) Secondo anno
1.GRASSI AURELIANO DIP. MATEMATICA PURA E APPLICATA DOTTORANDO 6 6
1.12.6 Personale extrauniversitario
nº Cognome Nome Dipartimento/Istituto Qualifica Mesi/Persona(*)
Primo anno
Mesi/Persona(*) Secondo anno
1.BOS LEONARD
P
Department of Mathematics and Statistics, University of Calgary, Canada
Full Professor 3 3
2.BREZINSKI CLAUDE Université des Sciences et Technologies, Laboratoire Paul Painlevé, Lille, France
Professor Emeritus
3 3
3.XU YUAN Department of Mathematics, Oregon University, USA Full Professor 3 3
PARTE II
2.1.0 Pubblicazioni scientifiche più significative dei componenti il gruppo di ricerca (docenti dell'ateneo di Padova)
nº Pubblicazioni Catalogo di
ateneo 1. BOS L, CALIARI M, DE MARCHI S, VIANELLO M., XU Y. (2006). "Bivariate Lagrange interpolation at the Padua points:
the generating curve approach". JOURNAL OF APPROXIMATION THEORY. vol. 143, pp. 15-25 ISSN: 0021-9045.
Classified in the Top 25 Hottest Articles of J. Approx. Theory, October-December 2006.
Impact factor .5
2. BOS L, DE MARCHI S, VIANELLO M., XU Y. (2007). "Bivariate Lagrange interpolation at the Padua points: the ideal theory approach". NUMERISCHE MATHEMATIK. vol. 108, pp. 43-57 ISSN: 0029-599X.
Impact factor 1.116
3. M. CALIARI, S. DE MARCHI, VIANELLO M. (2008). "Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains". ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE. vol. 35-3 ISSN: 0098-3500.
Impact factor 1.298
4. SLOAN I.H, SOMMARIVA A. (2007). Approximation on the sphere using radial basis functions plus polynomials.
ADVANCES IN COMPUTATIONAL MATHEMATICS. pp. ? ISSN: 1019-7168. In press.
Impact factor .868
5. SOMMARIVA A., VIANELLO M. (2006). Meshless cubature by Green's formula. APPLIED MATHEMATICS AND COMPUTATION. vol. 183, pp. 1098-1107 ISSN: 0096-3003.
Impact factor .816
6. SOMMARIVA A., VIANELLO M. (2007). Gauss-Green cubature over spline curvilinear polygons. BIT. vol. 47, pp. 441-453 ISSN: 0006-3835.
Impact factor .841
2.1.1 Pubblicazioni scientifiche più significative dei componenti il gruppo di ricerca (altri partecipanti al progetto)
** BOS Leonard P. **
BOS L., CALIARI M., DE MARCHI S., VIANELLO M. (2006)
"Bivariate interpolation at Xu points: results, extensions and applications". ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS, 25 (2006) 1-16.
BOS L., DE MARCHI S., VIANELLO M. (2006)
"On the Lebesgue constant for the Xu interpolation formula". J. APPROX. THEORY, 141 (2006) 134-141.
BOS L., CALIARI M., DE MARCHI S., VIANELLO M., XU Y.(2006)
"Bivariate Lagrange interpolation at the Padua points: the generating curve approach". J. APPROX. THEORY, 143 (2006) 15-25.
** BREZINSKI Claude **
BREZINSKI C., REDIVO-ZAGLIA M. (2006)
“The PageRank vector: properties, computation, approximation, and acceleration”. SIAM J. MATRIX ANAL.. APPL., 28 (2006) 551-575.
BREZINSKI C., REDIVO-ZAGLIA M. (2008)
“Rational extrapolation for the PageRank vector”. MATH. COMP., 77 (2008) 1585--1598.
BREZINSKI C., RODRIGUEZ G., SEATZU S. (2008)
“Error estimates for linear systems with applications to regularization”. NUMER. ALGORITHMS, 49 (2008), to appear.
** CALIARI Marco **
CALIARI M, DE MARCHI S, VIANELLO M., XU Y. (2006).
"Bivariate Lagrange interpolation at the Padua points: the generating curve approach". J. APPROX. THEORY, 143 (2006) 15-25. Classified in the Top 25 Hottest Articles of J. Approx. Theory, October-December 2006.
CALIARI M, DE MARCHI S, VIANELLO M. (2007)
“Bivariate Lagrange interpolation at the Padua points: computational aspects”, J. COMPUT. APPL. MATH., online 23 Oct. 2007.
CALIARI M., DE MARCHI S., VIANELLO M. (2008).
"Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains". ACM TRANS. MATH. SOFTWARE. vol. 35-3.
** DE MARCHI Stefano **
BOS L., DE MARCHI S., VIANELLO M. (2006)
"On the Lebesgue constant for the Xu interpolation formula". J. APPROX. THEORY, 141 (2006) 134-141.
BOS L., CALIARI M., DE MARCHI S., VIANELLO M., XU Y. (2006)
"Bivariate Lagrange interpolation at the Padua points: the generating curve approach". J. APPROX. THEORY,. 143 (2006) 15-25.
BOS L., DE MARCHI S., VIANELLO M., XU Y. (2007)
"Bivariate Lagrange interpolation at the Padua points: the ideal theory approach”. NUMER. MATH., 108 (2007) 43-57.
** DELL’ACCIO Francesco **
CAIRA R., DELL’ACCIO F. (2007)
“Shepard--Bernoulli operators”. MATH. COMP., 76 (2007) 299-321.
COSTABILE F.A., DELL’ACCIO F. (2007)
“New embedded boundary-type quadrature formulas for the simplex”, NUMER. ALGORITHMS, 45 (2007) 253-267.
COSTABILE F.A., DELL’ACCIO F. (2007)
“Polynomial approximation of functions by means of boundary values and applications: a survey”. J. COMPUT. APPL. MATH., 210 (2007) 116-135.
** RODRIGUEZ Giuseppe **
RODRIGUEZ G. (2006)
“Fast solution of Toeplitz- and Cauchy-like least squares problems”. SIAM J. MATRIX ANAL.. APPL., 28 (2006) 724-748.
HANSEN P.C., JENSEN T.K., RODRIGUEZ G. (2006)
“An adaptive pruning algorithm for the discrete L-curve criterion”. J. COMPUT. APPL. MATH., 198 (2006) 483-492.
Van der MEE C.V.M., RODRIGUEZ G., SEATZU S. (2006)
“Fast superoptimal preconditioning of multiindex Toeplitz matrices”. LINEAR ALGEBRA APPL., 418 (2006) 576-590.
** XU Yuan **
XU Y. (2006)
"A direct approach to the reconstruction of images from Radon projections", ADVANCES IN APPLIED MATHEMATICS. vol 36, pp. 388-420.
DUNKL C.F., XU Y. (2001)
Orthogonal Polynomials of Several Variables, Encyclopedia of Mathematics and its Applications 81, Cambridge University Press, Cambridge.
XU Y. (1994)
Common Zeros of Polynomials in Several Variables and Higher Dimensional Quadrature, Pitman Research Notes in Mathematics Series, Longman, Essex.
2.2 Curriculum scientifico dei Componenti il Gruppo di Ricerca Lingua Italiana
** SOMMARIVA Alvise **
Diplomi:
- Dottorato in Matematica Computazionale", 1999, Università di Padova.
- Laurea in "Matematica", 1993, Università di Padova.
Borse:
- Assegno di ricerca: "Analisi Numerica of integral and differential models of applied sciences" (1999-2002), Università di Padova.
- Post-dottorato: "Fast methods for integral equations", Dip. di Matematica Pura ed Applicata, Università di Padova (2002-2004). Dal 1 febbraio 2004 al 1 aprile 2004 ha collaborato con Kendall Atkinson all'University of Iowa.
- Research Associate: School of Mathematics, UNSW (Australia) (Settembre 2004-Dicembre 2005).
Posizione Attuale:
- Ricercatore in Analisi Numerica (MAT 08): Università di Padova (dal 1 Marzo 2006).
Attività scientifica:
Durante il Dottorato, la sua attività di ricerca ha riguardato una famiglia di equazioni integrali quadratiche della teoria del trasporto tra cui l'equazione H di Chandrasekhar e un caso puramente integrale dell'equazione di Boltzmann. In seguito si è interessato di solutori veloci per equazioni integrali nonlineari e sommazione di serie di potenze.
Recentemente sta lavorando su punti approssimati di Fekete, interpolazione e cubatura con polinomi, RBF su domini e varietà come simplessi, rettangoli, n-sfere e poligoni come pure su metodi di Galerkin per equazioni semilineari ellittiche (collaborando con K. Atkinson, R.
Womersley, I.H. Sloan e M. Vianello).
Attività di referee:
Numerische Matematik, IMA Journal Numerical Analysis, Journal of Integral Equations and Applications, Electronic Transactions in Numerical Analysis, Computing, Applied Numerical Mathematics, Numerical Algorithms.
Pubblicazioni:
Autore di più di 20 articoli nel campo dell’Analisi Numerica. Per la lista completa si veda http://www.math.unipd.it/~alvise/.
Organizzazione di Congressi:
- Organizzatore del 1st Dolomites Workshop on Constructive Approximation and Applications (DWCAA06) e della Dolomites Research Week on Approximation 2007 (DRWA07), Alba di Canazei (Trento, Italy), Sett. 2006 and 2007.
** MARCO VIANELLO **
CV in breve
- Nato a Venezia il 26/10/1961.
- Ph.D. in Matematica Computazionale, Università di Padova 1992.
- Borsista senior INdAM 1991-1993.
- Ricercatore (1993-2000) e Associato (2000-) di Analisi Numerica presso la Facoltà di Scienze dell'Università di Padova.
RISULTATI DI RICERCA
Autore di 73 lavori nei campi dell'Analisi Numerica e dell'Analisi Matematica, argomenti : 1. Approssimazione multivariata: polinomi, radial basis functions, cubatura numerica (20 lavori)
2. Approssimazione di funzioni esponenziali di matrice e integratori esponenziali per ODEs/PDEs (8 lavori) 3. Metodi di sommazione rapida (7 lavori)
4. Metodi costruttivo-numerici per equazioni integrali (6 lavori)
5. Analisi asintotica qualitativa e quantitativa: eq./sistemi differenziali e alle differenze del secondo ordine, funzioni speciali (23 lavori) 6. Analisi numerica in spazi astratti (9 lavori)
ESPERIENZE DI COLLABORAZIONE E COORDINAMENTO
- Supervisore di 2 tesi di Dottorato (A. Sommariva, M. Caliari) e di 3 borsisti post-doc in Matematica Computazionale.
- Collaborazioni internazionali con L. Bos (Calgary), C. Brezinski (Lille), W. Gautschi (Purdue), S. Waldron (Auckland), Y. Xu (Eugene).
- Coordinatore scientifico di 2 progetti di ricerca (fondi: 60000 euro).
- Coordinatore del CAA: Padova-Verona Research Group on Constructive Approximation and Applications.
- Membro del Collegio docenti del Dottorato in Matematica Computazionale dell'Università di Padova (2005-).
ORGANIZZAZIONE DI CONVEGNI ED ESPERIENZA EDITORIALE
- Membro dei comitati organizzatore e scientifico dei 1st Dolomites Workshop on Constructive Approximation and Applications (DWCAA06), Dolomites Research Week on Approximation 2007 and 2008 (DRWA07-08), Alba di Canazei (Trento), settembre 2006, 2007 and 2008.
- Guest editor dei Proceedings di DWCAA06, volume speciale di Numer. Algorithms.
Lingua Inglese
** SOMMARIVA Alvise **
Degrees:
- Ph.D. in "Computational Mathematics", 1999, University of Padua, Italy.
- B.Sc. in "Mathematics", 1993, University of Padua, Italy.
Positions held:
- Research Fellowship: "Numerical analysis of integral and differential models of applied sciences" (1999-2002), Universiy of Padua, Italy.
- Post-Doc Fellowship: "Fast methods for integral equations", Department of Pure and Applied Mathematics, University of Padua (2002-2004).
During such scolarship he has collaborated with K.Atkinson and has been visiting student at the Univ.of Iowa between Feb.1, 2004 and April 1, 2004.
- Research Associate: School of Mathematics, UNSW (Australia) (September 2004-December 2005).
Current Position:
- Assistant Professor in Numerical Analysis: University of Padua, Italy (from March 2006).
Referee Activity:
Numerische Matematik, IMA Journal Numerical Analysis, Journal of Integral Equations and Applications, Electronic Transactions in Numerical Analysis, Computing, Applied Numerical Mathematics, Numerical Algorithms.
Scientific activity:
During the Ph.D., his research activity has been focused on studying a family of quadratic integral equations arising in transport theory, including the Chandrasekhar H-equation and a pure integral instance of the Boltzmann equation. Afterwards, he has focussed his interests on fast solvers for nonlinear integral equations as well as some summation methods.
Recently he is working on approximate Fekete points, interpolation and cubature by polynomials and RBF on multivariate domains (and manifolds) as simplices, rectangles, n-spheres and polygons, as well as Galerkin methods for semilinear elliptic equations (collaborating with K. Atkinson, R. Womersley, I.H. Sloan and M. Vianello).
Publications:
Author of more then 20 Numerical Analysis papers. For a list see http://www.math.unipd.it/~alvise/.
Conference Organization:
Member of the organizing committees 1st Dolomites Workshop on Constructive Approximation and Applications (DWCAA06) and of the Dolomites Research Week on Approximation 2007 (DRWA07), Alba di Canazei (Trento, Italy), Sept. 2006 and 2007.
** MARCO VIANELLO **
Short CV
- Born in Venice on october 26, 1961.
- Ph.D. in Computational Mathematics, University of Padova 1992.
- INdAM research fellowship from november 1991 to october 1993.
- Assistant professor (1993-2000) and associate professor (2000-) of Numerical Analysis at the Faculty of Science of the University of Padova.
RESEARCH RESULTS
Author of 73 papers in the fields of Numerical Analysis and Mathematical Analysis, topics : 1. Multivariate approximation: polynomials, radial basis functions, numerical cubature (20 papers) 2. Approximation of matrix exponentials and exponential integrators for ODEs/PDEs (8 papers) 3. Fast summation methods (7 papers)
4. Constructive-numerical methods for integral equations (6 papers)
5. Qualitative and quantitative asymptotics: 2nd order differential and difference eqs./systems, special functions (23 papers) 6. Numerical analysis in abstract spaces (9 papers)
RESEARCH COLLABORATION AND CORDINATION EXPERIENCE
- Supervisor of 2 Ph.D. theses (A. Sommariva, M. Caliari) and of 3 post-doc fellowships in Computational Mathematics.
- International collaborations with L. Bos (Calgary), C. Brezinski (Lille), W. Gautschi (Purdue), S. Waldron (Auckland), Y. Xu (Eugene).
- Scientific coordinator of 2 research projects (grants: 60000 euros).
- Coordinator of the CAA: Padova-Verona Research Group on Constructive Approximation and Applications.
- Member of the Council of the Ph.D. program in Computational Mathematics of the University of Padova (2005-).
CONFERENCE ORGANIZATION AND EDITORIAL EXPERIENCE
- Member of the organizing and scientific committees of the1st Dolomites Workshop on Constructive Approximation and Applications (DWCAA06), Dolomites Research Week on Approximation 2007 and 2008
(DRWA07-08), Alba di Canazei (Trento, Italy), september 2006, 2007 and 2008.
- Guest editor of the Proceedings of DWCAA06, special issue of "Numer. Algorithms".
2.3 Stato dell'Arte: base di partenza scientifica nazionale ed internazionale Lingua Italiana
Si riporta una descrizione delle basi scientifiche del progetto, suddivisa nei due principali argomenti (i riferimenti bibliografici si trovano nella sezione 2.4).
1) Interpolazione polinomiale multivariata
L’interpolazione polinomiale multivariata è un filone di ricerca della teoria dell’approssimazione particolarmente attivo e con molti problemi aperti. Diversamente dal caso 1d, come sottolineato anche da De Boor in una recente comunicazione [deBo07], è piuttosto difficile cercare insiemi che siano unisolventi per l’interpolazione in 3d e in altri domini standard 2d. Ancora più complicato è trovare “buoni” punti per l’interpolazione.
Un primo passo in questa direzione è stato compiuto da alcuni dei partecipanti, studiando i punti proposti da Xu per l’interpolazione in un sottospazio dei polinomi di grado totale [Xu96, Bos&al06A], e provando che la loro costante di Lebesgue cresce come O(log^2(n)), dove n è il grado [Bos&al06C].
I “punti di Padova” nel quadrato sono stati un punto di svolta. Tali punti, proposti in [Cali&al05], sono stati analizzati dal punto di visto teorico e computazionale da alcuni partecipanti [Bos&al06B-07,Cali&al07C-08]. Non sono note generalizzazioni ad altri domini 2d e 3d.
Un’altra direzione recente consiste nel calcolare “punti approssimati di Fekete” [Bjor96], massimizzando il determinante di Vandermonde, con un algoritmo greedy basato su fattorizzazioni QR [Somm&al08]. Tale metodo, che ha basi teoriche in [Calv&al07, Bos&al08], è molto più efficiente che calcolare tali punti nel continuo. La sua versione complessa potrebbe essere interessante come metodo alternativo nell’interazione tra approssimazione polinomiale complessa e teoria del potenziale, con applicazioni al calcolo di equilibri discreti su continui del piano, filtri digitali per signal processing e sistemi lineari malcondizionati, ... [Embr&al99, Shen&al01, Berk&al04, Saad06].
Un altro argomento interessante connesso all’interpolazione polinomiale ma non molto sviluppato, eccetto per la sfera, è l’iperinterpolazione polinomiale [Sloa95]. In quest’ambito abbiamo già studiato nuove formule di iperinterpolazione [Cali&al06-07A-07B, DeMa&al08], come pure generalizzazioni della formula di Clenshaw-Curtis [Tref08, Somm&al07, DeMa&al08].
2)Metodi di estrapolazione: strumenti e applicazioni.
I metodi di estrapolazione [Brez&al91] costituiscono un’area dell'analisi numerica connessa con molti altri importanti argomenti (approssimanti di Padé, metodi di proiezione, …). Oltre ad accelerare la convergenza di successioni (di scalari, vettori o matrici) essi forniscono nuovi metodi risolutivi per altri problemi.
Particolare attenzione è stata rivolta in passato a nuovi approcci per trovare trasformazioni di successioni già note ed ottenerne di nuove, in particolare per i vettori [Brez&al96-04B-07B]. Strumenti utili per trovare nuove trasformazioni di successioni sono stati il complemento di Schur e la sua estensione a matrici rettangolari e alcune proprietà quali l'identità di Sylvester [Brez&al03A, Redi04, Redi&al08].
Un'importante applicazione dei metodi di estrapolazione è l'accelerazione dei metodi iterativi per la ricerca sul Web. Il più noto algoritmo è il PageRank (usato da Google) e lo strumento matematico utilizzato è il metodo delle potenze. Ma la dimensione è elevata e la convergenza risulta lenta. Una possibilità per accelerare tale processo è data dall'uso di metodi di estrapolazione [Brez&al05-06A-06B-07A-08].
Un'altra applicazione che ha dato ottimi risultati nel caso di un parametro[Brez&al98], ma che deve essere ancora approfondita nel caso multiparametro [Brez&al03B] riguarda la regolarizzazione di sistemi lineari mal condizionati (un problema che ha applicazioni in numerosi settori: image restoration, medical imaging, ...).
Molti dei temi di ricerca riguardano matrici strutturate. Una versione beta di un Matlab toolbox (SMT), specializzato nel trattamento di tali matrici è stato scritto da due dei partecipanti.
Lingua Inglese
A description of the scientific background by main topics follows (the references can be found in Section 2.4).
1) Multivariate polynomial interpolation
Multivariate polynomial interpolation is a particularly active research field in approximation theory, with several open problems. Differently from the 1d case, as indicated also by C. de Boor in a recent talk [deBo07], already the problem of finding unisolvent interpolation point sets in 3d and in 2d standard domain is quite difficult. Even more difficult is the problem of finding "good" interpolation points.
A first step in this direction was made by some of the participants, studying the points proposed by Y. Xu for interpolation in a subspace of total degree polynomials [Xu96, Bos&al06A], and proving that their Lebesgue constant grows like O(log^2(n)), n being the degree [Bos&al06C].
A turning point was given by the so-called "Padua points" in the square. Such points, proposed in [Cali&al05], have been deeply analyzed by some participants from both the theoretical and the computational point of view [Bos&al06B-07, Cali&al07C-08]. Generalizations to 2d/3d geometries are unknown.
Another very recent direction consists in computing "approximate Fekete points" [Bjor96] by maximizing the Vandermonde determinant, by a greedy algorithm based on QR factorization [Somm&al08]. This method, which has theoretical foundation in [Calv&al07, Bos&al08], is much more efficient than computing continuum Fekete points. Its complex version could be interesting as an alternative method in the interaction of complex polynomial approximation with potential theory and applications: computing discrete equilibria on planar continua, digital filters for signal processing and ill-conditioned linear systems, matrix functions, ... [Embr&al99, Shen&al01, Berk&al04, Saad06].
Connected to polynomial interpolation there is also the very interesting but yet not much developed topic of polynomial hyperinterpolation [Sloa95] (apart for the sphere). Here we have already worked on the construction of new hyperinterpolation formulas [Cali&al06-07A-07B, DeMa&al08], as well as on the generalizations of the Clenshaw-Curtis formula [Tref08, Somm&al07, DeMa&al08].
2) Extrapolation methods: tools and applications
Extrapolation methods [Brez&al91] now are a specific area of numerical analysis having connections with many other important topics (Padé approximation, projection methods, ...). Besides convergence acceleration of (scalar, vector or matrix) sequences, they can also furnish new solution methods for different problems.
In the past, particular attention was given to new approaches for recovering known sequence transformations and obtaining new ones, in particular in the vector case [Brez&al96-04B-07B]. Useful tools that lead to new vector sequence transformations have been the Schur complement and its extension to rectangular matrices, and some determinantal properties like the Sylvester determinantal identity [Brez&al03A, Redi04, Redi&al08].
An important application of extrapolation methods is the acceleration of iterative methods used in Web search. The most popular algorithm is the PageRank (used by Google), and the power method is the mathematical tool used. But the dimension is huge and the convergence is slow.
One possibility for accelerating this process is to use extrapolation methods, like in [Brez&al05-06A-06B-07A-08].
Another application that gave optimal results in the one parameter case [Brez&al98], but that deserves additional study in the multiparameter case [Brez&al03B], is the regularization of an ill-conditioned linear system (a problem that have applications to several domains: image restoration, medical imaging, ...).
Most of the research items concern with structured matrices. A beta version of a Matlab toolbox (SMT) specialized for managing such matrices has been written by two participants.
2.4 Descrizione del Programma di Ricerca Lingua Italiana
Si desidera sviluppare nuovi algoritmi avanzati nelle seguenti aree:
1) Interpolazione polinomiale multivariata
2) Metodi di estrapolazione: strumenti e applicazioni
Vi è un forte legame tra tali argomenti, sinora sviluppati in modo indipendente dai due gruppi di ricerca che con tale progetto desiderano collaborare per trarre vantaggio dalle competenze e dall’esperienza acquisita. Sia nella parte relativa all’interpolazione che in quella relativa all’estrapolazione, si desidera studiare e produrre nuovi algoritmi (ed il relativo software) per problemi di algebra lineare numerica.
Le principali caratteristiche del progetto sono:
- un nucleo di 3 ricercatori locali molto attivi, M. Redivo-Zaglia (responsabile, prof. associato), M. Vianello (prof. associato) e A. Sommariva (ricercatore), che ha pubblicato 6 libri e oltre 130 articoli di ricerca (più di 30 articoli su algoritmi in teoria dell’approssimazione nel 2005-2007);
- una rete consolidata di collaborazioni internazionali con esperti riconosciuti in teoria dell’approssimazione, di cui 3 partecipanti direttamente al progetto:
* L. Bos (Calgary, Canada), autore di vari articoli fondamentali in teoria dell’approssimazione multivariata;
* C. Brezinski (Lille, Francia), esperto mondiale nei metodi di estrapolazione, polinomi ortogonali ed algebra lineare numerica;
* Y. Xu (Eugene, USA), uno dei più noti ricercatori nel campo emergente dei polinomi ortogonali multivariati e loro applicazioni;
- una forte propensione verso la produzione di software numerico validato, usando (e migliorando) le risorse del nuovo NumLab (Laboratory for Numerical Applications, numlab.math.unipd.it) del Dipartimento di Matematica Pura ed Applicata;
- l’organizzazione di conferenze e scuole estive, con particolare attenzione a programmi di dottorato e post-doc.
1) Interpolazione e collocazione polinomiale multivariata
Il proposito ambizioso di questa sezione è di trovare “buoni punti”, cioè la cui costante di Lebesgue cresca poco, ed algoritmi efficienti per l’interpolazione polinomiale in domini multidimensionali.
In questo problema della teoria dell’interpolazione multivariata abbiamo recentemente trovato un punto di svolta con i "punti di Padova" nel quadrato, il primo esempio noto di punti unisolventi 2d la cui costante di Lebesgue ha crescita di ordine minimo O(log^2(n)) [Bos&al06B-07, Cali&al05-07C-08].
In una recente comunicazione [deBo07], C. De Boor ha indicato come problema aperto di notevole interesse la costruzione di insiemi di punti quasi ottimali in 3d (ad esempio nel cubo) e in altri domini standard come cerchio e triangolo.
Desideriamo usare vari approcci per risolvere tale problema. Nel primo, si cercherà di trovare costruzioni geometriche, analoghe a quella dei punti di Padova, in altri domini 2d (triangolo, cerchio) e 3d (cubo, simplesso, palla).
Un altro approccio consisterà nel calcolare “punti di Fekete approssimati” [Bjor96], massimizzando il determinante di Vandermonde (in certe basi polinomiali) su un insieme discreto sufficientemente denso, con un algoritmo greedy basato su fattorizzazioni QR [Somm&al08]. Il metodo, che ha basi teoriche nella recente teoria delle `mesh ammissibili’ per l’approssimazione polinomiale [Calv&al07] e nei risultati di [Bos&al08], è molto più efficiente che calcolare i punti nel continuo in quanto si devono risolvere problemi di ottimizzazione nonlineare di grandi dimensioni [Tayl&al00]. Inoltre, la sua versione complessa potrebbe avere un ruolo importante nell’interazione tra l’approssimazione polinomiale complessa e la teoria del potenziale e sue applicazioni: il calcolo di equilibri discreti in continui del piano, filtri digitali per signal processing e sistemi lineari malcondizionati, funzioni di matrici, ... [Embr&al99, Shen&al01, Berk&al04, Saad06].
Si desidera anche continuare il lavoro sul fruttuoso legame tra iperinterpolazione polinomiale [Sloa95] , cioè espansioni di Fourier discrete in polinomi ortogonali multivariati [Dunk&al01], e cubatura algebrica di grado elevato, in particolare la costruzione di nuove formule iperinterpolatorie [Cali&al06-07A-07B, DeMa&al08], come pure generalizzazioni della formula di Clenshaw-Curtis [Tref08, Somm&al07, DeMa&al08].
Un’ambiziosa prospettiva a lungo termine è di sviluppare nuovi strumenti per metodi polinomiali globali per PDEs (di tipo collocazione e spettrale), adattati in modo naturale alla particolare geometria del dominio.
2) Metodi di estrapolazione: strumenti e applicazioni
In diversi ambiti scientifici si devono spesso trattare successioni e serie che convergono molto lentamente, e questo costituisce un forte limite al loro effettivo utilizzo. Questo è il motivo per cui
i metodi di accelerazione della convergenza sono stati studiati per molti anni ed applicati a diverse situazioni. Essi sono anche connessi con molti altri importanti argomenti (approssimazione di Padé, frazioni continue, polinomi ortogonali formali, metodi di proiezione, …). I metodi di estrapolazione sono anche alla base di nuovi metodi risolutivi per problemi di altra natura (altrimenti irrisolvibili), nel campo dell'Ingegneria, Fisica, Chimica, Statistica, Economia, Biomatematica ecc. ed hanno numerose applicazioni (si veda, ad esempio [Bertelle&al07], e per una panoramica, [Brez&al91]). Oggi, in Italia, solo poche persone si occupano di metodi di estrapolazione e di accelerazione della convergenza e quasi tutti partecipano a questo progetto.
Negli ultimi anni, una particolare attenzione è stata rivolta alla costruzione di nuovi metodi di estrapolazione per successioni, soprattutto vettoriali [Brez&al96-04B-07B]. Ma i relativi algoritmi ricorsivi devono ancora essere determinati, programmati con estrema accuratezza, e confrontati con quelli esistenti. Questo è uno degli scopi di tale progetto. Per raggiungerlo si dovranno anche cercare risultati teorici di convergenza e di accelerazione, generalmente non facili da ottenere, e generalizzazioni di strumenti dell'algebra lineare, quali i complementi di Schur, le identità di determinantali, e così via (per alcuni risultati ottenuti, si veda [Brez&al03A, Redi04, Redi&al08]).
Relativamente alle applicazioni, particolare attenzione sarà data a due argomenti:
-Accelerazione dei metodi iterativi per il calcolo di autovettori di matrici stocastiche, in particolare per il PageRank di Google.
Tutti i principali motori di ricerca Web attualmente utilizzano la link analysis della struttura a grafo, che è basata su concetti fondamentali della teoria delle matrici, per migliorare i risultati della ricerca Il più noto algoritmo è il PageRank (usato da Google), sviluppato nel 1998 e migliorato da successive proposte per velocizzarlo. Dal punto di vista matematico, il calcolo del PageRank consiste nel determinare l’autovettore di una matrice che corrisponde al suo autovalore dominante unitario. A tale scopo viene attualmente usato il metodo delle potenze. Ma il problema principale è che la dimensione è elevata (8x10^9) e la convergenza risulta lenta. Inoltre, poiché il grafo che rappresenta il web è soggetto a modifiche importanti in termini di nodi e connessioni, il Page Rank tende a diventare obsoleto molto rapidamente e necessita di frequenti aggiornamenti (molti giorni di calcoli) ed il problema diventa malcondizionato quando, come richiesto, il parametro della matrice tende ad 1. Una possibilità per accelerare tale processo è data dai metodi di estrapolazione. Questi metodi [Brez&al05-06A-06B-07A-08] devono essere studiati in dettaglio. Nuove idee per nuovi algoritmi (rho-algorithm, frazioni continue ottenute con la procedura di interpolazione di Thiele, tecniche di “restarting”, …) saranno sviluppate, e testate, anche su macchine parallele per ridurre i tempi di calcolo.
Inoltre, si desidera trovare possibili applicazioni delle stesse tecniche di estrapolazione ad altri campi che hanno problematiche simili (matrici stocastiche e riducibili): complex networks, problemi di agglomerazione di virus, affidabilità dei sistemi industriali, …
- Una ben nota tecnica per risolvere i sistemi lineari malcondizionati è la regolarizzazione. Quando il parametro di regolarizzazione tende a zero, la soluzione del sistema regolarizzato converge verso la soluzione esatta. Sfortunatamente, se si prende un valore piccolo per il parametro, la soluzione è mal calcolata, se si prende un valore grande, la soluzione è ben calcolata, ma è molto differente dalla soluzione esatta.
Un problema importante è dunque la scelta del parametro di regolarizzazione. In [Brez&al98], alcuni partecipanti hanno messo a punto una tecnica di estrapolazione che consiste nel calcolare la soluzione per differenti valori del parametro, e successivamente ad estrapolare in zero. I risultati numerici ottenuti sono risultati particolarmente validi e la tecnica, innovativa.
Un primo tentativo di estendere tale tecnica al caso di parametri multipli (che permettono l'utilizzo contemporaneo di più matrici di regolarizzazione) è stato proposto in [Brez&al03B], ma necessita di ulteriori approfondimenti e l’individuazione, lo studio ed il test di algoritmi di estrapolazione per soluzioni regolarizzate di sistemi malcondizionati nel caso multiparametro è un altro obiettivo della ricerca.
Molti degli argomenti sono legati alle matrici strutturate. Lo scorso anno due dei partecipanti hanno rilasciato una versione beta di un toolbox Matlab object oriented, specializzato per tali matrici, ponendo particolare cura alla facilità d'uso, all'integrazione con l'ambiente Matlab e le sue routine ed all'ottimizzazione dei tempi di elaborazione e di occupazione di memoria, focalizzandosi su alcune tipologie di matrici strutturate e su algoritmi di base per la risoluzione di sistemi lineari con metodi iterativi precondizionati. Tale toolbox, chiamato SMT (Structured Matrices Toolbox), consente di utilizzare matrici strutturate in modo trasparente, utilizzando operazioni aritmetiche implementate con algoritmi veloci. Il pacchetto, fornito con un set di matrici test e con la generazione dei più comuni precondizionatori, è ottenibile nella sua versione preliminare sul sito bugs.unica.it/smt.
Si prevede di estenderlo con altre classi di matrici strutturate (Hankel, Vandermonde, ...), inserendo per esse un'implementazione ottimizzata dei migliori algoritmi veloci attualmente disponibili.
Bibliografia
[Berk&al04] M.K. Berkenbusch & al., Discrete charges on a two dimensional conductor, J. Stat. Phys. 116 (2004).
[Bertelle&al07] R. Bertelle, M.R. Russo, An approach to the Gummel map by vector extrapolation methods, Numer. Algorithms 45 (2007).
[Bjor96] A. Bjorck, Numerical Methods for Least Squares Problems, SIAM, 1996.
[Bos&al06A] L. Bos, S. De Marchi, M. Vianello, On the Lebesgue constant for the Xu interpolation formula, J. Approx. Theory 141 (2006).
[Bos&al06B] L. Bos, M. Caliari, S. De Marchi, M. Vianello, Y. Xu, Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006).
[Bos&al06C] L. Bos, M. Caliari, S. De Marchi, M. Vianello, Bivariate interpolation at Xu points: results, extensions and applications, ETNA 25 (2006).
[Bos&al07] L. Bos, S. De Marchi, M. Vianello, Y. Xu, Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer.
Math., 108 (2007).
[Bos&al08] L. Bos, N. Levenberg, On the Approximate Calculation of Fekete Points: the Univariate Case, submitted.
[Brez&al91] C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, 1991.
[Brez&al96] C. Brezinski, M. Redivo Zaglia, Vector and matrix sequence transformations based on biorthogonality, Appl. Numer. Math. 21
(1996).
[Brez&al98] C. Brezinski, M. Redivo Zaglia, G. Rodriguez, G. Seatzu, Extrapolation techniques for ill-conditioned linear systems, Numer. Math.
81 (1998).
[Brez&al03A] C. Brezinski, M. Redivo Zaglia, A Schur complement approach to a general extrapolation algorithm, Linear Algebra Appl., 368 (2003).
[Brez&al03B] C. Brezinski, M. Redivo Zaglia, G. Rodriguez, G. Seatzu, Multi-parameter regularization techniques for ill-conditioned linear systems, Numer. Math. 94 (2003).
[Brez&al04B] C. Brezinski, M. Redivo Zaglia, New vector sequence transformations, Linear Algebra Appl. 389 (2004).
[Brez&al05] C. Brezinski, M. Redivo Zaglia, S. Serra-Capizzano, Extrapolation methods for Pagerank computations, Comptes Rendus Mathem., 340 (2005).
[Brez&al06A] C. Brezinski, M. Redivo Zaglia, The PageRank vector: properties, computation, approximation, and acceleration, SIAM J. Matrix Anal. Appl. 28 (2006).
[Brez&al06B] C. Brezinski, M. Redivo Zaglia, Some numerical analysis problems behind web search, Transgressive Computing 2006, Granada.
[Brez&al07A] C. Brezinski, M. Redivo Zaglia, Extrapolation and minimization procedures for the PageRank vector. In: Web Information Retrieval and Linear Algebra Algorithms, Dagstuhl, Feb. 2007.
[Brez&al07B] C. Brezinski, M. Redivo Zaglia, Generalizations of Aitken's process for accelerating the convergence of sequences. J. Comput.
Appl. Math. 26 (2007).
[Brez&al08] C. Brezinski, M. Redivo Zaglia, Rational extrapolation for the PageRank vector, Math. Comp.77 (2008).
[Cali&al05] M. Caliari, S. De Marchi, M. Vianello, Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput. 165 (2005).
[Cali&al06] M. Caliari, S. De Marchi, R. Montagna, M. Vianello, HYPER2D: a numerical code for hyperinterpolation at Xu points on rectangles, Appl. Math. Comput. 183 (2006).
[Cali&al07A] M. Caliari, S. De Marchi, M. Vianello, Hyperinterpolation on the square, J. Comput. Appl. Math. 210 (2007).
[Cali&al07B] M. Caliari, S. De Marchi, M. Vianello, Hyperinterpolation in the cube, Comput. Math. Appl. 55 (2008), 2490--2497.
[Cali&al07C] M. Caliari, S. De Marchi, M. Vianello, Bivariate Lagrange interpolation at the Padua points: computational aspects, J. Comput.
Appl. Math., online 23 Oct. 2007.
[Cali&al08] M. Caliari, S. De Marchi, M. Vianello, Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math.
Software 35-3 (2008).
[Calv&al07] J.P. Calvi, N. Levenberg, Uniform approximation by discrete least squares polynomials, J. Approx. Theory, online 8 Dec. 2007.
[deBo07] C. de Boor, Issues in multivariate polynomial interpolation, plenary talk at "Stanford 50", March 2007 (http://www.stanford.edu/group /compmath50).
[DeMa&al08] S. De Marchi, M. Vianello, Y. Xu, New cubature formulae and hyperinterpolation in three variables, submitted.
[Dunk&al01] C.F. Dunkl, Y. Xu, Orthogonal Polynomials of Several Variables, Enc. Math. & Appl. 81, Cambridge Univ. Press, 2001.
[Embr&al99] M. Embree, L.N. Trefethen, Green¹s Functions for Multiply Connected Domains via Conformal Mapping, SIAM Rev. 41 (1999).
[Redi04] M. Redivo Zaglia, Pseudo-Schur complements and their properties, Appl. Numer. Math. 50 (2004).
[Redi&al08] M. Redivo Zaglia, M.R. Russo, Generalizations of Sylvester’s determinantal identity, submitted.
[Saad06] Y. Saad, Filtered conjugate residual-type algorithms with applications, SIAM J. Matrix Anal. Appl. 28 (2006).
[Shen&al01] J. Shen, G. Strang and A. Wathen, The Potential Theory of Several Intervals and Its Applications, Appl. Math. Optim. 44 (2001).
[Sloa95] I.H. Sloan, Interpolation and Hyperinterpolation over General Regions, J. Approx. Theory 83 (1995).
[Somm&al07] A. Sommariva, M. Vianello, R. Zanovello, Nontensorial Clenshaw-Curtis cubature, Numer. Algorithms, online 27 May 2008.
[Somm&al08] A. Sommariva, M. Vianello, Computing approximate Fekete points by QR factorizations of Vandermonde matrices, submitted.
[Tayl&al00] M.A. Taylor, B.A. Wingate and R.E. Vincent, An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal. 38 (2000).
[Tref08] L.N. Trefethen, Is Gauss quadrature better than Clenshaw-Curtis? SIAM Rev. 50 (2008).
[Xu96] Y. Xu, Lagrange interpolation on Chebyshev points of two variables, J. Approx. Theory 87 (1996).
Lingua Inglese
We plan to develop new advanced approximation algorithms, and the related software, in the following areas:
1) Multivariate polynomial interpolation 2) Extrapolation methods: tools and applications
There is a strong connection between these subjects, up to now developed independently by two research groups that, with this project, try to collaborate together for take advantage of their knowledge and experience. In the interpolation part and also in the extrapolation part, we want to study and to produce new algorithms (and the related software) for numerical linear algebra problems.
The main features of the project are:
- a core of 3 very active local researchers, M. Redivo-Zaglia (responsible, associate professor), M. Vianello (associate professor) and A.
Sommariva (assistant professor), who have published 6 books and over 130 research articles (more than 30 papers on approximation algorithms in 2005-2007);
- a consolidated network of international collaborations with recognized experts in approximation theory, 3 participating directly in the project:
-- L. Bos (Calgary, Canada), author of several fundamental papers in the theory of multivariate polynomial approximation;
-- C. Brezinski (Lille, France), leading expert in the fields of modern extrapolation methods, orthogonal polynomials and numerical linear algebra;
-- Y. Xu (Eugene, USA), one of the most known researchers in the emerging field of multivariate orthogonal polynomials and their applications;
- a strong commitment towards the production of validated numerical software, by using (and improving) the resources of the new NumLab (Laboratory for Numerical Applications) at the Dept. of Pure and Applied Mathematics (http://numlab.math.unipd.it/);
- the organization of conferences and summer schools, with special attention to Ph.D. and post-doc programs.
