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.
1) Multivariate polynomial interpolation and collocation
The ambitious goal of this section is to find "good" points, i.e.
unisolvent points whose Lebesgue constant grows slowly, and efficient
algorithms for polynomial interpolation in multidimensional domains.
This is an open problem of multivariate interpolation theory [deBo07],
where we have recently found a break-through by the so-called "Padua
points" in the square, which are the first known example of unisolvent
2d points whose Lebesgue constant has minimal order of growth
O(log^2(n)) [Bos&al06B-07, Cali&al05-07C-08].
In a recent talk [deBo07], C. de Boor has indicated as noteworthy open
problems the construction of similar near-optimal point sets in 3d
(e.g. in the cube), as well as in other standard 2d domains like the
disk and the triangle.
We plan to attack the problem from different sides. One will be for
example trying to find some geometric construction analogous to that of
the Padua points, in other 2d domains (triangle, disk) and in 3d (cube,
simplex, ball). Another will be computing "approximate Fekete points"
[Bjor96] by maximizing the Vandermonde determinant (in suitable
polynomial bases) on a sufficiently dense discrete set, by a greedy
algorithm based simply on QR factorizations of Vandermonde matrices
[Somm&al08]. This method, which has theoretical foundation in the
recent theory of "admissible meshes" for polynomial approximation
[Calv&al07] and in the results of [Bos&al08], is much more
efficient than computing continuum Fekete points which involve
large-scale nonlinear optimization problems [Tayl&al00]. Moreover,
its complex version could play a significant role in the interplay 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].
We plan also to continue our work on the fruitful interplay of
polynomial hyperinterpolation [Sloa95] , that is discretized Fourier
expansions in multivariate orthogonal polynomials [Dunk&al01], and
high-degree algebraic cubature, namely 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].
One of the long-term ambitious perspectives is to develop new tools in
global polynomial methods for PDEs (collocation and spectral-like),
naturally adapted to the specific domain's geometry.
2) Extrapolation methods: tools and applications
In several scientific domains, one has often to deal with sequences and
series, that converge so slowly that it is a serious drawback to their
effective use. This is the reason why convergence acceleration methods
have been studied for many years, and applied to various situations.
They are also related to many other important topics (Padé
approximation, continued fractions, formal orthogonal polynomials,
projection methods, ...). Extrapolation methods form the basis of new
methods for solving various problems (unsolvable otherwise), also in
Engineering, Physics, Chemistry, Statistics, Economics, Biomathematics
and so on, and have many applications as well (see, for example
[Bertelle&al07]), and, for an overview, [Brez&al91]). Nowadays,
in Italy, only very few people work on extrapolation methods and
convergence acceleration and almost all of them participate to this
program.
In the past, particular attention was given in obtaining new
extrapolation methods, overall for vector sequences,
[Brez&al96-04B-07B]. But recursive algorithms for these methods
have to be obtained, programmed with great care, and compared to the
existing ones. This is one of the main aims of this subject in this
project. For doing that, we also have to look at theoretical results on
convergence and acceleration, not so easy to obtain, in general, and
generalizations of several Linear Algebra tools, such as Schur
complements, determinantal identities, and so on (for some obtained
results, see [Brez&al03A, Redi04, Redi&al08]).
With regards to applications, a particular attention will be given to two main subjects:
- Acceleration of iterative methods for eigenvectors of stochastic
matrices computation, in particular for the Google’s PageRank.
All the major Web search engines today use link analysis of the Web’s
hyperlink structure to improve search results, and a link analysis is
built from fundamentals of matrix theory. The most popular link
analysis algorithm is the PageRank (used by Google), developed around
1998, improved by the successive techniques proposed to speed-up this
algorithm. From the mathematical point of view, computing the rank of
the pages consists in finding the eigenvector of a matrix corresponding
to its dominant eigenvalue which is equal to 1. The power method is
actually used for this purpose. But, the main problem is that the
dimension is huge (8x10^9) and the convergence is slow. Moreover, since
the Web graph is subject to dramatic updates in terms of nodes and
links, the PageRank assignment tends to become obsolete very soon, and
it needs frequent updates (several days of computations!), and the
problem becomes ill-conditioned when, as required, the parameter of the
Google matrix tends to 1.One possibility for accelerating it, is to use
extrapolation methods. These extrapolation methods
[Brez&al05-06A-06B-07A-08] have to be studied in more details. New
ideas (rho-algorithm, continued fractions obtained by Thiele
interpolation process, restarting, …) have to be developed and tested,
possibly on parallel computers, for reducing the computational time.
In addition, we want to look at possible applications of the same
extrapolation techniques to other domains that have similar problems
(stochastic reducible matrices): complex networks, viruses
agglomeration, reliability of industrial systems, and so on.
- Ill-conditioned linear systems.
A well known technique for solving an ill-conditioned linear system is
the regularization. When the regularization parameter tends to zero,
the solution of the regularized system converges to the exact solution.
Unfortunately, if the parameter is close to zero, then, due to the
ill–conditioning, the solution is badly computed while, if the
parameter is far away from zero, the solution is well computed but it
is very different from the exact solution. Thus, the choice of a good
value for the parameter is an important problem. In [Brez&al98], a
joint work with three of the participants of this project, we computed
the regularized solutions for several values of the regularization
parameter and then we extrapolated at zero. The numerical results
obtained proved the effectiveness of this innovative technique.
A first attempt for extending this technique to the multiparameter case
(that allows to add simultaneously several regularization terms) has
been proposed in [Brez&al03B], but it needs of additional study and
test, and this is another goal of the proposed research.
Several of the proposed research subjects are related to
structured matrices and their treatment. Last year, two of the
participants, released a beta version of an object oriented specialized
Matlab toolbox. Particular attention was made to an user-friendly use,
to the compatibility with the Matlab environment and with the intrinsic
computing functions, and to the optimization of the computing time and
memory requirements, focusing first on few structured matrices and on
the basic algorithms for the solution of linear systems by using
preconditioned iterative methods. This toolbox, named SMT (Structured
Matrices Toolbox), allows to use the structured matrices in a natural
way, by using the arithmetic operations implemented through fast
algorithms. The package has been completed with a test matrices set and
with the most common preconditioners. It can be obtained in its beta
version on the page http://bugs.unica.it/smt/.
Now we want to extend it by including more classes of structured
matrices (Hankel, Vandermonde, displacement structure, ...), inserting
also for the an optimized implementation of the available best fast
algorithms for solving structured algebraic problems.
References
[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).