Abstract - Algebra Lineare Numerica e Applicazi
Algebra Lineare Numerica e Applicazioni
a Roma Tor Vergata
Roma Tor Vergata, 29-30-31 Gennaio 2013
Sommari delle comunicazioni come pervenuti
(Cliccare sul titolo per accedere alle slides)
Stefania Bellavia (Universita' degli Studi di Firenze)
A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems
We analyze and discuss matrix-free and limited-memory preconditioners (LMP) for sparse symmetric positive definite systems and normal equations of large and sparse least-squares problems. The preconditioners are based on a partial Cholesky factorization and can be coupled with a deflation strategy. The construction of the preconditioners requires only matrix-vector products, is breakdown-free, and does not need to form the matrix. The memory requirements of the preconditioners are defined in advance and they do not depend on the number of nonzero entries in the matrix. In case eigenvalue deflation is used, the preconditioners turn outto be suitable for solving sequences of slowly changing systemsor linear systems with different right-hand sides. Numerical results are shown, including the case of sequences arising in constrained linear least-squares problems solved by interior point
Joint work with Jacek Gondzio and Benedetta Morini
Luca Bergamaschi (Universita' di Padova)
Metodi di tipo Newton precondizionati per problemi agli autovalori.
In collaborazione con Angeles Martinez (Universita' di Padova).
We propose to compute a few eigenpairs of large SPD matrices by using the Inexact Newton method for the constrained minimization of the Rayleigh Quotient. We are particularly concerned with the issue of efficient preconditioning of the linearized Newton systems. We construct a sequence of preconditioners based on successive BFGS-like rank-two updates of an initial preconditioner, computed for the coefficient matrix A. We theoretically show that the distance of the preconditioned Jacobians from the identity matrix do not deteriorate with the nonlinear iteration index. Numerical results onto matrices of large size arising from various engineering applications show that the proposed sequence of preconditioners yield an improvement of total iteration number and CPU time of a factor three with respect to using the same initial preconditioner (Incomplete Cholesky with fill-in) at every Newton iteration.
Pasqua D'Ambra (ICAR-CNR, Napoli)
Adaptive AMG with coarsening based on compatible weighted matching
We introduce a new composite adaptive Algebraic Multigrid method (alpha-AMG) to solve systems of linear equations without a-priori knowledge or assumption on characteristics of near-null components of the preconditioned problem referred to as algebraic smoothness. Our version of alpha-AMG is based on a bootstrap strategy aimed to obtain a composite AMG with desired convergence rate. Each new hierarchy built during the bootstrap process relies on a pairwise aggregation scheme based on weighted matching in a graph and on principles of compatible relaxation, which replace the commonly used characterization of strenght of connection among variables in both the coarse space selection and in the interpolation scheme. The final goal is to design a method leading to efficient and scalable AMG for a wide class of problems that include linear systems arising from anisotropic Partial Differential Equations (PDEs) as well as non-scalar or non-elliptic systems. We will introduce the method and demonstrate its potential when applied to symmetric positive definite linear systems arising from finite element discretization of highly anisotropic elliptic PDEs on structured and unstructured meshes.
joint work with Panayot S. Vassilevski, CASC-LLNL, Livermore, USA
Valentina De Simone (Seconda Universita' di Napoli)
A matrix-free approach to build band preconditioners for linear systems arising in optimization
We are interested in preconditioning linear systems arising from the application of truncated Newton iterations in trust-region or line-search frameworks for large-scale bound-constrained optimization problems. We assume that the working set may change significantly at each outer step and that the system matrix is not esplicitly available or is too large to be stored in the main memory. Therefore, preconditioning techniques exploiting information from previous steps, either matrix-free such as Hessian approximations based on limited-memory BFGS, or requiring explicit knowledge of (part of) the matrix such as updates of incomplete factorizations, cannot be easily applied. We present a recursive approach to build symmetric positive-definite band preconditioners for symmetric, possibly indefinite, matrices by using few matrix-vector products and sufficient conditions for positive definiteness. This approach has been applied within the TRON trust-region Newton method by Lin and Moré, showing its effectiveness.
Lavoro in collaborazione con Daniela Di Serafino
P. Dell'Acqua (Universita' dell'Insubria)
Image restoration: Z variant for iterative and direct regularization methods
Iterative deblurring algorithms that use the conjugate transpose A^H of the coefficient matrix A show usually a slow convergence. A variant which replaces A^H with a new matrix Z is proposed. This approach, which is linked with preconditioning theory and reblurring processes, can be applied to a wide set of iterative methods. Computational tests show that this strategy leads to a significant improvement of the convergence speed of the methods. It is noteworthy that it can be naturally combined with other widely used acceleration techniques. Moreover the use of the Z variant idea can be successfully employed for direct filtering methods, like Tikhonov.
Gianna Del Corso (Universita' di Pisa)
Trasfomazioni di matrici quasi normali a forma tridiagonale a blocchi
Una matrice quasi normale e' una matrice per la quale esiste una correzione di rango basso C, tale che A'A-AA'=CA-AC. In generale la matrice di Hessenberg associata a tali matrici e' densa anche se strutturata. In questa comunicazioni daremo delle condizioni necessarie e sufficienti per ridurre unitariamente le matrici quasi normali a matrici tridiagonali a blocchi. Mostreremo inoltre come queste trasformazioni possono essere ottenute con un procedimento algoritmico basato sul metodo di Lanczos a partire da particolari vettori di partenza. Queste riduzioni possono costituire una valida alternativa alla riduzione a forma di Hessenberg in quanto si nota una conservazione della struttura con passi di QR.
In collaborazione con Roberto Bevilacqua e Luca Gemignani
Fabio Di Benedetto (Università di Genova)
Precondizionamento e altre varianti al metodo di Landweber in spazi di Banach
I metodi di regolarizzazione negli spazi di Hilbert danno luogo a soluzioni estremamente regolari (over-smoothness), poco adatte a fenomeni quali la ricostruzione di immagini, dove i bordi di un oggetto rappresentano discontinuita' "naturalmente'' presenti.
Piu' recentemente, la formulazione del problema inverso di ricostruzione in spazi L^p, con 1<p<2, ha permesso di ottenere soluzioni meno soggette al fenomeno di over-smoothness. Nella ricostruzione di immagini il contrasto e la risoluzione dei bordi degli oggetti risulta di conseguenza migliore.
In questa comunicazione presenteremo il metodo di regolarizzazione iterativa di Landweber in spazi di Banach; mostreremo in particolare come le tecniche di precondizionamento note possano essere adattate al nuovo contesto.
Illustreremo infine una nuova proposta che trasforma una variante, inizialmente pensata in altri contesti allo scopo di aumentare la regolarizzazione, in una tecnica che ottiene l'effetto opposto di migliorare i contrasti. Quest'ultimo argomento e' oggetto di una ricerca ancora in progress.
Lavoro in collaborazione con P. Brianzi, A. Di Stefano, C. Estatico
Daniela Di Serafino (Seconda Universita' di Napoli)
A class of preconditioners for sequences of diagonally modified linear systems with applications to optimization
We are interested in preconditioning sequences of large and sparse linear systems, where the matrices are obtained by a diagonal positive semidefinite perturbation of a symmetric positive semidefinite matrix A. We look for effective alternatives to freezing the preconditioner for consecutive matrices of the sequence, which is costless but may yield convergence slowdown, or to recomputing the preconditioner for each matrix, which may be too expensive and uselessly accurate. We propose a new class of preconditioners that are obtained by low-cost updates of a preconditioner for the matrix A, available in the LDL' factorized form. The preconditioners in this class are effective on slowly varying sequences and, by satisfying an additional property, they are able to cluster eigenvalues of the preconditioned matrix when entries of the diagonal perturbation matrix are sufficiently large. We present more in detail two preconditioners in this class and show their effectiveness on sequences of linear systems arising in the solution of bound-constrained convex quadratic programming problems by the reflective Newton method and in the solution of nonlinear least-squares problems by the regularized Euclidean residual method.
Lavoro in collaborazione con Stefania Bellavia, Valentina De Simone, Benedetta Morini
Marco Donatelli (Universita' dell'Insubria)
An iterative multigrid regularization method for deblurring problems.
Iterative regularization multigrid methods have been successful applied to signal/image deblurring problems. The smoother has to be an iterative regularization method, while the grid transfer operator should preserve the regularization property of the smoother. In this talk we consider a wavelet soft-thresholding denoising post-smoother constructed from the multigrid grid transfer operator. Such post-smoother improves the restoration and avoids the noise amplification that is the cause of the semi-convergence of iterative regularization methods. The resulting iterative multigrid method stabilizes the iterations so that and imprecise (over) estimate of the stopping iteration does not have a deleterious effect on the computed solution. The proposed algorithm is quite flexible since it is independent of the imposed boundary conditions and nonnegativity constraints can be easily included.
Massimiliano Fasi (Collegio Superiore, Bologna)
Numerical methods for the Lambert W function on matrices
The Lambert W function is a not-so-widely-known special function, implicitly defined by the equation z = W(z)e^W(z), that has an elegant formulation as well as very good regularity properties. Since we are particularly interested in the matrix case, we will underline the issues of the existing non-iterative algorithm, based on the definition of matrix function via eigendecomposition, and will propose an iterative Newton-like method that generalizes the Schur-Parlett approach to functions where the choice of the initial value is region- dependent. Some theoretical results on Newton iteration for matrices will be given, along with a little survey of the still open problems for both the scalar and matrix case.
joint work with Bruno Iannazzo (Università di Perugia) and Nicola Guglielmi (Università dell'Aquila)
Dario Fasino (Università di Udine)
La distanza di resistenza in reti complesse ad elevata connettività algebrica.
L'inversa di Moore-Penrose della matrice laplaciana di un grafo interviene nel calcolo di vari indici di centralità e altre quantità interessanti nell'analisi di reti complesse. Mostriamo che questa matrice è "vicina" alla somma di una matrice diagonale con una matrice di rango basso (1 o 2) quando la connettività algebrica (cioé il più piccolo autovalore positivo del laplaciano) del grafo è "grande" in rapporto al massimo grado dei suoi nodi. Questo fatto risulta utile, p.es., nello studio di indici di vulnerabilità e della "distanza di resistenza" per nodi di grafi sparsi e di grandi dimensioni.
Salvatore Filippone (Università di Roma Tor Vergata)
Approximate Inverse Preconditioners for Sparse Linear Systems
The development of effective preconditioners is an essential tool in solving large and sparse linear systems arising in many application fields.
We review methods for building preconditioners based on approximate inverse factorization of large and sparse matrices. We present a detailed analysis of the computational and numerical behaviour in the context of novel computing architectures.
In particular, we present a new formulation of the biconjugation algorithm of Benzi and Tuma, based on a left-looking variant, and we demonstrate its potential both in terms of numerical behaviour and of runtime performace.
Lavoro in collaborazione con Daniele Bertaccini (Universita' di Roma Tor Vergata)
Carlo Garoni (Universita' dell'Insubria, Como)
Matrici di stiffness provenienti dall'IgA: analisi spettrale e progettazione di efficienti metodi multigrid
L'analisi isogeometrica (IgA) si sta affermando come metodo alternativo a quello degli elementi finiti per la risoluzione numerica dei problemi differenziali. In questa comunicazione verrà presentata un'analisi delle proprietà spettrali di alcune matrici di stiffness provenienti dall'IgA. Uno dei fini di questa analisi è quello di costruire buoni precondizionatori e buoni metodi multigrid per la risoluzione veloce dei sistemi lineari associati alle matrici di stiffness dell'IgA. A questo proposito, verrà illustrato un modo per costruire un metodo multigrid a due livelli (two-grid) dal quale ci si aspettano buone proprietà di convergenza (confermate dalle sperimentazioni numeriche).
Lavoro in collaborazione con: Carla Manni, Francesca Pelosi, Stefano Serra-Capizzano, Hendrik Speleers.
Luca Gemignani (Universita' di Pisa)
Il metodo di Ehrlich--Aberth per il calcolo dei valori singolari.
In questa comunicazione discutiamo l'applicazione del metodo di Ehrlich-Aberth per il calcolo dei valori singolari di una matrice. Attenzione sara` posta sulle proprieta` strutturali e sull'accuratezza della risoluzione del problema tridiagonale agli autovalori associato al calcolo dei valori singolari.
Vanni Noferini (Manchester University)
Alcune considerazioni sul root-finding
Nella prima parte del talk si discuteranno alcuni esperimenti numerici relativi al problema di trovare le radici reali dell'equazione f(x)=0. Nella seconda parte del talk si passerà ad analizzare il caso degli autovalori reali di una matrice i cui elementi sono funzioni. Il talk è basato sullo stato preliminare di una ricerca in corso.
Lavoro in collaborazione con Y. Nakatsukasa (Manchester) e A. Townsend (Oxford).
Silvia Noschese (Sapienza Università di Roma)
Sottospazi invarianti: problemi inversi e applicazioni
Data una matrice quadrata [hermitiana] A, si vuole determinare la matrice [hermitiana] piu vicina ad A nella norma di Frobenius con un sottospazio invariante assegnato. Vengono discusse applicazioni ai metodi di Krylov per la soluzione di sistemi lineari e di problemi agli autovalori. Si considerano inoltre estensioni a matrici rettangolari, e applicazioni riguardanti la bidigonalizzazione di Lanczos e la regolarizzazione di problemi malposti discreti.
Federico Poloni (Università di Pisa)
Interpretazioni probabilistiche e algoritmi accurati per code fluide
Consideriamo il modello di una cosiddetta /fluid queue/, cioè un contenitore infinito in cui la quantità di liquido cresce o decresce a una velocità v_i che dipende dallo stato di una catena di Markov che modella l'ambiente. Studiamo un algoritmo per il calcolo dei livelli medi asintotici di fluido basato sullo structured doubling algorithm (SDA).
Sebbene questo algoritmo sia derivato con idee astratte di algebra lineare, mostriamo che le iterate ammettono un'interessante interpretazione in termini di probabilità. Questa interpretazione aiuta a comprendere intuitivamente il comportamento dell'algoritmo, a dimostrare le sue proprietà di convergenza, e può essere usata per migliorare l'accuratezza dell'algoritmo.
Lavoro in collaborazione con Giang T. Nguyen (Adelaide University)
Filippo Pompili (Universita' di Perugia)
Fattorizzazione nonnegativa matriciale con vincoli geometrici e applicazioni.
Recentemente le tecniche di fattorizzazione matriciale con vincoli di nonnegatività (NMF: nonnegative matrix factorization) sono state applicate alla riduzione della dimensionalità, al clustering di documenti testuali e più in generale al data mining. Una linea di sviluppo della NMF propone l'introduzione di ulteriori vincoli di ortogonalità che si dimostrano più efficaci della soluzione standard nelle prestazioni di classificazione non supervisionata e nell'estrazione delle features. Verranno presentate tecniche di soluzione numerica del nuovo problema che sfruttano le caratteristiche geometriche dell'insieme dei vincoli di ortogonalità; in particolare vengono applicate tecniche di ottimizzazione su varietà Riemanniana. Verranno illustrate anche possibili generalizzazioni del modello nonnegativo alla segmentazione di dati di risonanza magnetica rappresentati da matrici definite positive.
Lavoro in collaborazione con P.-A. Absil, N. Gillis, F. Glineur (Université Catholique de Louvain, Belgio), B. Iannazzo (Universita' di Perugia), B. Jeuris (KU Leuven, Belgio)
Marina Popolizio (Universita' del Salento, Lecce)
Tecniche di aggiornamento adattivo per l'approssimazione di funzioni di grandi matrici
Vari problemi applicativi richiedono la valutazione di funzioni di matrici di grandi dimensioni e sparse. Per questo, un gran numero di metodi sono stati proposti durante gli ultimi anni. Spesso sono stati ottenuti buoni risultati sfruttando approssimazioni razionali. Noi proponiamo alcune tecniche di accelerazione per il calcolo di f(A) o di f(A)b con f(A) approssimata da una forma razionale, A ha elementi reali non necessariamente simmetrica e b e' un vettore. Queste tecniche sono proposte sia per approssimare direttamente f(A) che come precondizionatori per metodi iterativi di tipo proiettivo. Entrambe le strategie operano prevalentemente in aritmetica reale e sono designate in modo da avere buone potenzialita' parallele. Verranno mostrati anche promettenti risultati preliminari. Le strategie da noi proposte sono state ispirate da e fondamentalmente basate su metodi per l'aggiornamento di fattorizzazioni incomplete generali proposti nell'ultimo decennio.
Lavoro in collaborazione con Daniele Bertaccini (Universita' di Roma Tor Vergata)
Margherita Porcelli (ISTI-CNR, Pisa)
New updates of incomplete LU factorizations and applications to large nonlinear systems
We address the problem of preconditioning sequences of large sparse indenite systems of linear equations and present two new strategies to construct approximate updates of factorized preconditioners for a reference matrix of the sequence. Both updates are based on the availability of an incomplete factorization for one matrix of the sequence and dier in the approximation of the so-called ideal updates. The rst strategy is an approximate diagonal update of the ILU factorization; the second strategy relies on banded approximations of the factors in the ideal update. Both strategies are compatible with nearly matrix-free implementations. The efficiency and reliability of the proposed preconditioners are shown in the solution of nonlinear systems of equations by preconditioned Newton-Krylov methods.
Lavoro in collaborazione con Stefania Bellavia, Benedetta Morini
Michela Redivo-Zaglia, Università di Padova
Vector generalizations of Shanks' transformation applied to Kaczmarz' method
The method of alternation projections (MAP) is an iterative procedure for finding the projection of a point on the intersection of closed subspaces of an Hilbert space. The convergence of this method is usually slow, and several methods for its acceleration have already been proposed. In this work, we consider a special MAP, namely Kaczmarz' method for solving systems of linear equations. The convergence of this method is discussed. After giving its matrix formulation and its projection properties, we consider several procedures for accelerating its convergence. They are based on sequence transformations whose kernels contain sequences of the same form as the sequence of vectors generated by Kaczmarz' method. Acceleration can be achieved either directly, that is without modifying the sequence obtained by the method, or by restarting it from the vector obtained by acceleration. Numerical examples show the effectiveness of both procedures.
This is a joint work with Claude Brezinski.
Leonardo Robol (SNS, Pisa)
Solving secular and polynomial equations: a multiprecision algorithm
We present a numerical algorithm to approximate all the solution of the secular equation \sum_{i=1}^n a_i/(x-b_i)-1=0 with any given number of guaranteed digits. Two versions are provided. The first relies on the MPSolve approach of [BF], the second on the approach of [F] for computing polynomial roots. Both versions are based on a rigorous backward error analysis and on the concept of root neighborhood combined with Gerschgorin theorems, where the properties of structured matrices are exploited. An implementation based on the GNU multiprecision package (GMP) is provided which is included in the release 3.0 of the package MPSolve of [BF]. The new release computes both the solutions of a secular equation and the roots of a polynomial assigned in terms of its coefficients. From the many numerical experiments, it turns out that the new release is generally much faster than MPSolve 2.0 and of the package Eigensolve of [F]. For certain polynomials, like the Mandelbrot or the partition polynomials [BG] the acceleration is dramatic. Partition polynomials of degree 70.000 are solved in less than 2 hours. The algorithm exploits the parallel architecture of the computing platform.
Lavoro in collaborazione con D.Bini.
[BF] D.A. Bini, G. Fiorentino, Design, analysis and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms, 23:127-173, 2000
[BG] R.P. Boyer and W.M.Y. Goh. Partition polynomials: asymptotics and zeros. Tapas in experimental mathematics, 99-111, Contemp. Math., 457, Amer. Math. Soc., Providence, RI, 2008.
[F] S. Fortune, An iterated eigenvalue algorithm for approximating the roots of univariate polynomials, Journal of Symbolic Computation 33, 5, 2002, 627-646.
M. Semplice (Universita' dell'Insubria)
Precondizionamento multigrid per PDE non lineari e applicazioni al degrado monumentale
Consideriamo sistemi lineari di grandi dimensioni, (localmente) strutturati, derivanti dalla linearizzazione di sistemi di equazioni non lineari ottenuti discretizzando equazioni paraboliche nonlineari (possibilmente degeneri) mediante differenze finite nello spazio e schemi impliciti in tempo.
Nella prima parte consideriamo una discretizzazione uniforme nello spazio. Usando la teoria delle sequenze di matrici (localmente) Toeplitz si studia lo spettro delle matrici Jacobiane del metodo di Newton dimostrandone la convergenza e derivando precondizionatori ottimali basati su tecniche multigrid. I test numerici sono condotti sull'equazione dei mezzi porosi e su una particolare equazione parabolica non lineare che modella la solfatazione del marmo da parte di agenti inquinanti[1,2].
Successivamente, spinti dalla presenza di uno strato limite nel modello di solfatazione, estendiamo i risultati precedenti al caso di discretizzazioni non uniformi nello spazio, usando precondizionatori basati sul multigrid algebrico. [3]
In collaborazione con M. Donatelli e S. Serra-Capizzano
[1] M. Donatelli, M. Semplice, S. Serra-Capizzano - Analysis of multigrid preconditioning for implicit PDE solvers for degenerate parabolic equazions - SIAM J. Matrix Anal. Appl. 32 (2011) 1125–1148
[2] M. Semplice - Preconditioned implicit solvers for nonlinear PDEs in monument conservation - SIAM J. Sci. Comp. 32 (2010) 3071- 3091
[3] M. Donatelli, M. Semplice, S. Serra-Capizzano - AMG preconditioning for nonlinear degenerate parabolic equations on nonuniform grids with application to monument degradation - Appl. Numer. Math. (in revisione)
Emilio Spedicato (Universita' di Bergamo)
Metodi ABS, stato dell' arte e prospettive
I metodi ABS, sviluppati a partire dal 1982 in una collaborazione fra l' università di Bergamo e matematici inglkesi, unghresi, cinesi e iraniani, sono documentati in circa 400 pubblicazioni e 2 monografie. La ricerca prosegue particolarmente in Iran sui problemi a variabili intere, dopo la soluzione ABS del decimo problema di Hilbert nel caso solubile lineare, nel 2001. Si da una rassegna dei metodi, di alcune looro applicazioni e di aree aperte per la ricerca futura.
Francesco Tudisco (Universita' di Roma Tor Vergata)
La proiezione di un cono autoduale su un sottospazio proprio
L'insieme dei vettori (matrici) ad elementi nonnegativi e' un cono autoduale di R^n (R^nxn). Lo studio della possibilita' di proiettare una matrice nonnegativa su un sottospazio mantenendone la nonnegativita' conduce a due nuove caratterizzazioni dei coni autoduali di uno spazio euclideo X, ed alla descrizione di tutti e soli quei sottospazi propri di X sui quali e' possibile proiettare un cono autoduale simpliciale rimanendo nel cono stesso.