|
|
|
|
|
|
|
|
|
Abstracts e slides
(Cliccare sul titolo per accedere alle slides)
La teoria ed i metodi dell'algebra lineare numerica trovano molteplici applicazioni nello studio delle reti complesse. Anzi, lo straordinario impulso che la ricerca sulle reti registra negli ultimi anni è stato favorito in modo determinante dalla disponibilità di affidabili strumenti numerici di semplice utilizzo.
In certi casi lo studio di una rete conduce a problemi di natura combinatoria, spesso NP-hard, per i quali un approccio numerico permette la sintesi di valide euristiche.
Il problema del calcolo di certi indici di centralità usati sopratutto per reti sociali, su cui ci concentriamo in questo intervento, è invece un problema (quasi) lineare ma la cui soluzione diretta è possibile solo per reti di dimensione contenuta.
In this talk we present two numerical methods to compute the band spectra of 2D
photonic crystals without impurities, a finite difference frequency domain
(FDFD) method and a finite element frequency domain (FEFD) method. Exploiting
periodicity to identify discretization points differing by a period, the
computational complexity of the algorithms is reduced significantly. Some
preliminary considerations on the extension of the FDFD method to the 3D case
are also presented.
By using one of the definitions of the Bernoulli numbers,
we observe that they solve particular odd and even lower
triangular Toeplitz (l.t.T.) systems.
In a paper Ramanujan writes down a sparse lower triangular
system solved by Bernoulli numbers; we observe that such system is
equivalent to a sparse l.t.T. system.
The attempt to obtain the sparse l.t.T. Ramanujan system
from the l.t.T. odd and even systems, leads us to study
efficient methods for solving generic l.t.T. systems.
In this talk we present new iterative regularization methods, based on the approximation of nonstationary iterated Tikhonov. In particular we investigate the image deblurring problem, where the blurring matrix is not easily invertible with a low computational cost, while an approximation with such property is available. This is for instance the case of block Toeplitz matrices with Toeplitz blocks that can be well approximated by block circulant matrices with circulant blocks matrices which can be diagonalized by two dimensional fast Fourier transforms. Matrices arising from the imposition of other boundary conditions can be considered as well.
A detailed analysis is proposed in the stationary case and we discuss relations with preconditioned Landweber method and other known methods. A large numerical experimentation with different boundary conditions, blurring phenomena and noise level is presented.
L’analisi di spettro singolare (Singular Spectrum Analysis, SSA) [3] è una tecnica per l’analisi di serie
temporali relativamente recente ma già diffusa in ambito statistico, basata sulla SVD di certe matrici
di Hankel, dette matrici traettoria. Uno degli aspetti interessanti della SSA è che le matrici traettoria
hanno rango basso, indipendente dalla loro dimensione, quando la serie temporale è costituita dal
campionamento di una qualsiasi combinazione lineare di termini algebrici, trigonometrici o esponenziali.
Vari aspetti teorici della SSA non sono del tutto chiari, per esempio, al riguardo del dimensionamento
ottimale delle matrici traettoria, delle informazioni contenute nei valori singolari, e della possibilità di
separare le varie componenti additive della serie temporale.
Nell’articolo [1] abbiamo mostrato un possibile collegamento tra SSA e analisi di Fourier, per mezzo
delle proprietà asintotiche degli autovalori di matrici di Toeplitz. Inoltre, in [2] sono stati conseguiti alcuni
risultati di perturbazione relativa dei valori singolari di matrici rettangolari, utili per la comprensione
della SSA di serie temporali risultanti dalla sovrapposizione di segnali elementari.
Bibliografia
[1] E. Bozzo, R. Carniel, D. Fasino. Relationship between singular spectrum analysis and Fourier
analysis: theory and application to the monitoring of volcanic activity. Comput. Math. Appl. 60
(2010), 812–820.
[2] V. Busoni. Risultati di tipo perturbativo nell’analisi dello spettro singolare di serie temporali. Tesi
di Laurea in Matematica, Università di Udine, 2011.
[3] N. Golyandina, V. Nekrutkin, A. Zhigljavsky. Analysis of time series structure. SSA and related
techniques. Chapman & Hall/CRC, 2001.
This talk is about numerical issues related to a classical problem of Computational Algebra, when limited precision data are involved.
Given a finite set X of points and a tolerance representing the maximum error on the coordinates of each point, we address the problem of computing a simple polynomial f whose zero-locus "almost'' contains the points of X.
For computing the polynomial f, we consider an ordered finite sequence of underdetermined nonlinear systems subject to constraints. Each nonlinear problem is solved using a modified version of the classical Normal Flow algorithm and involves linear systems which often turn out to be ill-conditioned. We overcome such numerical difficulties computing the numerical rank of the coefficient matrices and using a rank revealing strategy. The relationship between the data tolerance and the parameters involved in the numerical rank detection is still an open issue.
Lo studio di vasti sistemi software ha potuto usufruire recentemente
dell'applicazione della teoria delle reti complesse. È infatti possibile
associare a un sistema software un grafo i cui nodi sono i moduli e gli archi
sono relazioni tra nodi. Vengono proposte prove numeriche su alcune metriche
caratteristiche delle reti complesse, alcune ampiamente conosciute e altre più
recenti, e metodologie per il loro calcolo.
In questo talk si illustrera' un metodo numerico per la risoluzione del
problema di Dirichlet per l'equazione di Laplace nel piano, su domini aventi
frontiera regolare a tratti. L'approccio consiste nell'approssimare la funzione
densitµa mediante un opportuno metodo di Nystrom, basato su una formula di
quadratura di tipo Lobatto, allo scopo poi di approssimare la soluzione del
problema iniziale come potenziale di doppio strato. La convergenza e la
stabilita' del metodo saranno discussi, il buon indice di condizionamento del
sistema lineare che si risolve sara' provato e differenti test numerici saranno
mostrati.
The search for efficient preconditioners for Krylov subspace methods is a theme underlying the numerical linear algebra research over the last decades. Recent developments, esp. in computing hardware, have revamped the interest in preconditioners based on sparse approximations of the linear system matrix A. We will discuss various alternative ways of computing an approximate inverse, outlining computation costs and preconditioning efficiency on conventional and innovative computing architectures, with reference to some representative problem classes.
Recently a novel parallel preconditioner for symmetric positive definite (SPD) matrices has been developed coupling a generalized Factored Sparse Approximate Inverse (FSAI) with an Incomplete Cholesky (IC) factorization. The generalized FSAI, called Block FSAI (BFSAI), is derived by requiring the preconditioned matrix to resemble a block-diagonal matrix in the sense of the minimal Frobenius norm. An incomplete Block Jacobi algorithm is then effectively used to accelerate the convergence of a Krylov subspace method giving thus rise to a completely parallel approach. Though its performance is usually superior to that of FSAI in most applications, BFSAI has the major drawback of requiring the a priori selection of a proper non-zero pattern which may not always be an easy task. An algorithm is developed that generates automatically the non-zero pattern of the BFSAI preconditioner. It is demonstrated that in SPD problems BFSAI minimizes an upper bound to the Kaporin number of the preconditioned matrix. This suggests an efficient and easily parallelizable Adaptive BFSAI (ABF) preconditioner for improving the given non-zero pattern of BFSAI.
Numerical experiments performed on large sized finite element problems show that ABF coupled with IC may outperform BFSAI-IC up to a factor 4 preserving the same preconditioner density and exhibiting an excellent parallelization degree.
Radiometer and scatterometer data are characterized by a spatial resolution that,
although adequate for many large-scale phenomena, is a severe limitation to observe
small-scale features.
Accordingly, we present effective techniques based on the two-dimensional TSVD
and the iterative regularization in Banach Space to generate added-value products
characterized by a spatial resolution finer that the intrinsic radiometer one.
Discuteremo l'applicazione di metodi 'root-finding' al calcolo degli autovalori di un polinomio di matrici P(x) con particolare attenzione al caso di polinomi strutturati. Test numerici mostrano che questo approccio porta ad un errore in avanti minore rispetto ai metodi tradizionali; inoltre si ottiene una maggiore efficienza se il grado del polinomio è alto.
Nel caso strutturato il metodo consente di estrarre esattamente la struttura spettrale, con lo svantaggio di una possibile perdita di cifre nell'approssimazione di un numero finito di autovalori detti 'eccezionali'.
A questo proposito presenteremo recenti risultati relativi a un algoritmo di tipo Newton, basato su una divisione polinomiale strutturata, per il raffinamento delle approssimazioni degli autovalori eccezionali.
Le matrici tridiagonali di Toeplitz compaiono in varie applicazioni, tra le quali la soluzione numerica di problemi differenziali. È certamente utile per il loro trattamento comprenderne a fondo proprietà rilevanti. L'analisi della sensibilità spettrale di una matrice di struttura data costituisce un fondamentale tema di ricerca in Algebra Lineare Numerica. Mostrerò espressioni esplicite ottenute in collaborazione con L. Pasquini e L. Reichel relative sia al condizionamento (tradizionale e strutturato) dello spettro che all'analisi dell'e-pseudospettro di una matrice tridiagonale di Toeplitz. Presenterò quindi un algoritmo che fa uso di tali formule, recentemente definito e analizzato in collaborazione con P. Buttà e N. Guglielmi, per il calcolo della ascissa e-pseudospettrale strutturata di una matrice tridiagonale di Toeplitz.
For the solution of discrete ill-posed problems, a preconditioned iterative method based on the Arnoldi algorithm for matrix functions is presented. The method is also extended to work in connection with Tikhonov regularization.
La risoluzione numerica dei problemi discreti lineari malposti richiede
l'impiego di tecniche di regolarizzazione. In tali metodi, il parametro di
regolarizzazione determina la qualita' dell'approssimazione fornita dalla
soluzione regolarizzata. In questa comunicazione verra' illustrato un
confronto numerico tra le prestazioni di vari metodi gia' noti per la
determinazione di un parametro di regolarizzazione discreto, e di alcune
tecniche recentemente introdotte. Tali criteri di scelta del parametro
verranno applicati alla decomposizione ai valori singolari troncata (TSVD) e al
metodo iterativo in spazi di Krylov noto come LSQR.
|
|
|
|
|
|
|
|
|
