Area Scientifico Disciplinare: Scienze Matematiche

Structured matrix analysis: numerical methods and applications

The mathematical modeling of problems of the real world often leads to solving numerical linear algebra problems where matrices endowed with specific structures and with very large dimensions are involved. That is, these matrices are defined by few parameters that characterize all their entries through a given pattern. The structures which appear in the mathematical model are the algebraic and formal counterparts of the specific features of the problem. The discover and the analysis of structured matrix properties is a fundamental step for the design and the analysis of very efficient algorithms for many computational problems where the customary methods are unusable for their large complexity and for the huge sizes involved.
The aim of this project is to analyze the algebraic, analytical and computational properties of classes of structured matrices in order to provide tools for the design and analysis of effective algorithms for solving different computational problems.
Particular interest is devoted to structures defined by displacement operators including Toeplitz-like and Hankel-like; more specifically, (multi-level) Toeplitz matrices with scalar/block entries, with finite/infinite size. Particular interest is devoted to the analysis of displacement operators and to matrix algebras related to discrete transforms, to spectral properties and to the design of preconditioners, to the study of multigrid methods, to the analysis of structures derived from the discretization of differential operators, to the properties of spectral factorizations in weighted Banach algebras. Other matrix structures of interest are diagonal plus semi-separable (DSS) matrices which have recently collected a growing interest.
The main computational problems concern the solution of finite, semi-infinite, and bi-infinite linear systems; the computation of matrix factorizations; the computation of eigenvalues and the inverse eigenvalue problem; the solution of matrix equations where the blocks are structured; the computation of spectral factorizations.
The results that we obtain will be applied to the solution of: problems in queueing theory, polynomial computations, say, (multivariate) polynomial factorization, numerical solution of differential and integral equations, analysis of neural networks, image restoration, solution of nonconstrained optimization problems.
The project aims to create prototype software for the numerical validation and comparison of the algorithms and to study the possibility of creating multiprecision algorithms for recursive polynomial factorization and for multigrid solvers.

TOEPLITZ MATRICES ; STRUCTURED MATRICES ; DISPLACEMENT RANK ; SPECTRAL FACTORIZATION ; PRECONDITIONING FOR STRUCTURED MATRICES ; NUMERICAL SOLUTION OF MARKOV CHAINS ; IMAGE RESTORATION ; POLYNOMIAL COMPUTATIONS ; MULTIGRID FOR STRUCTURED MATRICES

Dario Bini is full professor of numerical analysis since 1986. He is author of about 70 papers, published in international journals and in proceedings of international conferences, and of several books in numerical analysis and computational mathematics. He is member of the editorial board of the international journal "Calcolo" and has a wide and long expertise in the research fields of structured matrix computations, design and analysis of numerical algorithms and polynomial computations. He has organized international conferences on these research topics. He has been advisor of several PhD thesis. His main research interests include, Toeplitz matrix computations, displacement operators, polynomial computations, numerical solution of Markov chains, solution of matrix equations.

1. BINI D.A., B. MEINI. (2001). Approximate displacement rank and applications.

In V. OLSHEVSKY. Structured matrices in mathematics, computer science, and engineering, II. (vol. 281, pp. 215--232). Contemporary Mathematics. PROVIDENCE ,RI: American Mathematical Society (UNITED STATES).
2. BINI D.A., GEMIGNANI L., MEINI B. (2001). Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations. NUMERISCHE MATHEMATIK. vol. 89 (2001), no. 1, pp. 49--82.
3. BINI D.A., L. GEMIGNANI, B. MEINI. (2001). Computations with infinite Toeplitz matrices and polynomials. LINEAR ALGEBRA AND ITS APPLICATIONS. vol. 343-344, pp. 21-61.
4. BINI D.A., MEINI B. (1999). Effective methods for solving banded Toeplitz systems. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. vol. 20, pp. 700-719.
5. BINI D.A., B. MEINI. (1996). On the solution of a nonlinear matrix equation arising in queueing problems. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. vol. 17, pp. 906-926.

The main goals of the project are:
-A- The analysis of structural, algebraic, analytic, spectral and computational properties of the most important classes of matrices with a structure (including Toeplitz-like, Hankel-like, with finite/infinite size, with scalar/block entries, multilevel, with a banded structure, with recursive structure, semiseparable etc) which are encountered in problems of pure and applied mathematics.
-B- Exploiting these properties in order to create new general methods for the design and analysis of efficient algorithms for computational problems with special attention devoted to applicative problems and large scale scientific computing.
-C- The application of the new algorithm designed in this way for solving some specific problems of theory and applications.
-D- Design of prototype software implementing the new algorithms in order to compare and validate the new techniques.
More specifically, for each goal listed above we have the following items:
A- Theoretical issues
A1 Analysis of structured matrix algebras, relations with fast discrete transforms, analysis of linear spaces more general than trigonometric algebras; design and analysis of displacement operators and inversion formulas with application to preconditioning. Analysis of the properties of the optimal preconditioner in matrix algebras. Extension of the result of Serra-Tyrtyshnikov about the impossibility of having strong clusters with multilevel circulant matrices. Approximate displacement rank and Newton's iteration.
A2 Spectral and structural analysis of sequences of (multilevel) Toeplitz-like matrices, analysis of Szego-like formulas. Generalization to matrix valued symbols (block matrices); extension of the concept of "locally Toeplitz" matrix to multilevel matrices with application to the solution of PDE (next item C3). Extension of the class of test functions in the distributional results for Toeplitz sequences.
A3 Analysis of the asymptotic conditioning of structured matrices. Analysis of Laplacian Graph matrices, analysis of the "structured conditioning" for sequences with a displacement structure (Cauchy-like, Vandermonde-like, Pick).
A4 Analysis of relationships between infinite dimensional problems expressed in the language of Operator Theory (following the Boettcher-Silbermann approach [BS]) and finite dimensional problem in asymptotic linear algebra with the goal of creating synergies between the two fields.
A5 Spectral factorization of multi-level (multi-index) Toeplitz matrices with scalar/block entries in weighted Wiener algebras. Analysis of the asymptotic behaviour of the coefficients in the factorization. Extension to the case of multi-index block matrices. Factorization and inversion of Laurent polynomials. Applications to the design of algorithms for solving semi-infinite multi-level Toeplitz systems (item B3) and to preconditioning (item B1).
A6 Analysis of direct and inverse eigenvalue problems for semiseparable matrices, QR factorization of Cauchy-like matrices. Relations with orthogonal rational functions.
B- Algorithmic issues
B1 Design and analysis of preconditioners for multilevel matrices. Analysis of preconditioners based on the concept of locally Toeplitz matrices (item A2) with application to the numerical solution of elliptic PDE with nonconstant coefficients (item C3). Analysis of preconditioners based on spectral factorization of infinite matrices. Analysis of the superoptimal preconditioner of Tyrtyshnikov, of the regularizing properties with application to image restoration (item C1). Analysis of the solution of ill-posed problems with multilevel matrices and with superoptimal preconditioners. Applications to computing eigenvalues of displacement-structured matrices based on isospectral flows and homotopic continuation.
B2 Design and analysis of multigrid methods for the solution of structured multilevel systems with main interest to Toeplitz+diagonal matrices and matrices in algebras. Application to image restoration problems (item C1).
B3 Design of algorithms for solving (multilevel) infinite Toeplitz systems with scalar/block entries. Methods based on the theory of matrix polynomals and on the technique of band extension. Methods based on spectral factorizations, methods based on cyclic reduction and Graeffe's iteration applied to Laurent polynomials. Methods for perturbed Toeplitz matrices with applications to PDE (item C3) and integral equations.
B4 Design of algorithms for matrix equations. Riccati-like equations, polynomial and power series equations. Design of deflation techniques; using properties of Frobenius matrices, of evaluation/interpolation and of A5,B3,B5 for the design of new methods.
B5 Polynomial computations. Using the results of A5,B3,B4 for designing fast factorization algorithms for polynomials and power series. Extension to matrix and multivariate polynomals. Relations between polynomial factorization and solving matrix equations (B4). Wilson's method and evaluation/interpolation at the Fourier points. Application of the techniques to solving Sylvester-like systems with scalar/block entries and to QR factorization of Cauchy-like matrices (item B6).
B6 Methods for computing the QR factorization of Cauchy-like matrices with application to problems of rational approximation (item C5).
C- Applications
C1 Image restoration and inverse problems. Structure analysis and applications of the results of A1,A2,B1 for the reconstruction of LBT images (Large Binocular Telescope). Using optimal preconditioners. Using chopping and nodding techniques for removing the background noise to infrared images.
C2 Integral equations. Solving integral equations with structured kernels related to the identification of underground inhomogeneities by means of acoustic and sismic methods by means of A2,A5,B3. Solving integral equations in inverse scattering problems in acoustics and in quantum mechanics.
C3 PDE. Application of A2,A5 and B1 to the numerical solution of PDE. Solving Helmholtz equation over a thin unbounded strip (wave propagation along waveguides). Design of preconditioners for systems arising from FD and FE discretization of PDE.
C4 Numerical solution of Markov chains in queueing problems. Structured matrix analysis in different models like M/G/1, G/M/1, QBD, BMAP, PH/PH/11, NonSkipFree and Tree; multilevel structures, recursive structures, application of A1, B4, B5 for the design of effective algorithms.
C5 Approximation and quadrature. Numerical quadrature of multivariate functions expressed in terms of their Fourier coefficients. Analysis of the asymptotic distribution of zeros of orthogonal polynomials. Approximate interpolation with rational functions by means of B6.
C6 Minimum problems. Using matrix algebras for approximating the Hessian in quasi-Newton minimum problems; applications to minimizing the error function in neural networks. Total least squares problems with structures.
D- Software
D1 Implementation, numerical validation and comparisons of the algorithms.
D2 Creating a set of test matrices.
D3 Creating a web page with links to the software, test matrices, benchmarks.
D4 Design of software for the recursive factorization of polynomials.
D5 Design of software for multigrid algorithms.

The mathematical modeling of problems of the real world often leads to solving linear systems of equations endowed with specific structures and with very large dimensions. Generally the matrices involved in these models are defined by few parameters that characterize all their entries through a given pattern. In fact, structured matrices are encountered in many problems of theoretical and applied mathematics, in different fields of scientific and technological research and in industrial mathematics. The structures which appear in the mathematical model are the algebraic and formal counterparts of the specific features of the problem. The discover and the analysis of structure properties is a fundamental step for the design and the analysis of very efficient algorithms where the customary methods are unusable for their large complexity and for the huge sizes involved. Great progress have been made in the last two decades in this direction (see for instance [BP], [BTY], [BvB], [CN], [HR], [KS], [KvB], [O]).
 

Certain structures are very frequent and reflect specific features that are common to problems arising in diverse fields of applied mathematics and engineering. Toeplitz matrices are an example of this fact. A matrix is Toeplitz if it has constant entries along each diagonal. This kind of matrices, with their block versions, arises whenever properties of shift invariance are satisfied by some function in the model. They are encountered, in particular, in fields like image processing, queueing theory, computer algebra and in the numerical solution of differential and integral equations where the shift invariance takes different forms.
 

Indeed, the stronger is the structure, the more likely efficient solution algorithms can be designed. A challenging problem is to analyze and exploit, as most as possible, the specific structures that characterize a problem in order to devise tools for the design of efficient solution algorithms.
 

Very often such structures are accompanied by further properties, like banded patterns or Kronecker product patterns that make the problem still more interesting. For block matrices we may have structures at two (or more) different levels: an inner structure, typical of each block, and an outer structure proper of the block matrix. Exploiting both structures is a nontrivial task as it could seem at first. Other similar structures are also encountered like Hankel, Cauchy, Frobenius, Vandermonde, Sylvester, Bezout, Loewner matrices and the semiseparable structures.
 

The theoretical results obtained in the last two decades in the research field of structured matrix analysis has produced very impressive advances in the design of fast algorithms, leading to a dramatic reduction of the cpu time needed for solving many computational problems; we refer to [BTY] and [KS] for a collection of the most recent achievements. Below we resume the most interesting fields where structure analysis has an important role or where we have recently had impressive achievements.
 

-- Queueing theory:
Many problems in queueing theory are modeled by MG1 and GM1 Markov chains where the peculiarity of the problem is reflected by a block Toeplitz structure in block Hessenberg form of the involved stochastic matrices [Ne], [LR]. Further features of the model (say, use of buffers, PH/PH/1, QBD, NonSkipFree properties) lead to additional structures (say, Kronecker, Frobenius, block tridiagonal etc) [BMR]. Matrices may be finite, semi-infinite or bi-infinite according to the indexing of the states. The achievements reached with the use of structured matrix analysis has led to speedups of several hundreds in the computer solution of concrete problems [BM3], [BM4], [KS], [M1].
 

-- Integral and differential equations:
Numerical discretization of differential equations often leads to solving large linear systems with a structured matrix (say, finite differences techniques applied to a linear differential operator with constant coefficients yield a banded Toeplitz matrix). Multidimensional problems (Partial Differential Equations) lead to multilevel (multi-index)Toeplitz matrices. Unbounded domains lead to matrices with infinite size. Operators with nonconstant coefficients or nonuniform discretizations produce more hidden structures as Toeplitz-like structures or locally Toeplitz matrices. Similar considerations hold for the discretization of integral equations with a (perturbed) convolution kernel. Methods based on structured matrix analysis (preconditioning and multigrid) have reduced to a constant value the number of iterations sufficient to get a significant approximation of the solution of the specific linear systems [ST], [FS], [CN].
 

-- Image restoration:
In many applications the problem of restoring a blurred and noisy image is encountered. The mathematical model often contains symmetries and shift invariance properties which lead to Toeplitz matrices or to their approximations [BeBo], [BDB]. This typically occurs if the Point Spread Function is spatially invariant. Impressive algorithmic improvements have been achieved thanks to the use of preconditioners in structured algebras [CN], [KS], [NPPT].
 

-- Matrix equations:
Matrix equations are encountered in a wide variety of research fields, including control theory, dynamic programming, stochastic filtering, statistics and queuing theory [HK]. A wide literature exists for specific classes of problems like Lyapunov, Riccati and Sylvester equations. Solving matrix equation is strictly related to the theory of matrix polynomials [GLR] and to Toeplitz computations [BM4]. Some of the most efficient algorithms recently introduced, are based on structured numerical linear algebra tools [M2].
 

-- Polynomial computations:
Many problems involving polynomials (say, factorization, computing gcd or lcm, stability analysis, counting roots in the unit disk, orthogonal polynomials) can be reduced to performing operations with structured matrices (Bezout, Sylvester, Vandermonde, Toeplitz, Hankel matrices) [BP], [BvB], [KvB]. The modern design and analysis of efficient algorithms for polynomial computations relies on tools in structured matrix analysis. Asymptotic orthonormalization processes, by means of the Gram-Schmidt method, of a sequence of multivariate functions obtained through shift of the variables leads to a limit profile. Computing this profile can be achieved by means of the spectral factorization of a multilevel Toeplitz matrix in a weighted Banach space [GMRS].
 

The interest for Toeplitz matrices with a multilevel structure, with scalar/block entries, with finite/semi-infinite/bi-infinite size is not just motivated by the applications. In fact, the peculiarities of this class of matrices endow them with rich analytical, spectral and algebraic properties which make this class particularly interesting from the theoretical point of view. A wide literature, with a lot of results and research lines well consolidated in the years, keeps enriching with relevant results either theoretical or computational, and provides a solid basis for this project. Specifically, we refer to the books by Bini and Pan [BP], Boettcher and Silbermann [BS], Bultheel and Van Barel [BvB], Grenander and Szego [GS], Heinig and Rost [HR], Gohberg Goldberg and Kaashoek [GGK], to the books edited by Bini Yalamov and Tyrtyshnikov, [BYT], Kailath and Sayed [KS], Olshevsky [O], to the review papers by Chan and Ng [CN], Kravanja and Van Barel [KvB], and to the references cited therein.
 

It is worth citing the following issues which have become indispensable tools for the design and analysis of effective algorithms for structured problems of large size:
 

-- The Szego asymptotic spectral theory (see [GS], [BS] and the literature cited therein);
-- The Schur complement properties and the theory of displacement operators, the inversion formulas, the discrete transforms and their relations with structured matrix algebras (see [HR], [BP], [KS] and the references cited therein);
-- Fast and superfast direct algorithms [KS], [GKO], [BP];
-- Effectively fast algorithms based on conjugate gradient [CN] and multigrid [FS];
-- The theory of structured preconditioning of the conjugate gradient, which has been enriched by the contributions of many research groups ([CN], [CPS], [DB], [DBS], [H], [KS], [TZ], [S1], [S2], [Str]);
-- The interplay between polynomial or power series computations and structured matrix computations ([BvB], [KvB], [BP], [B], [BGM], [BGM1]) which allows to reformulate the operations with polynomials in terms of structured matrices and vice-versa;
-- The analysis of infinite systems, of spectral factorizations of structured Banach algebras with infinite dimension with the related convergence problems [GGK], [BS], provides a research field where we still have relevant achievements.
 

The growing interest in structured matrix analysis and computations is also confirmed by the numerous conferences and workshops devoted to this research area which have been organized in the last few years. Many national and international research groups perform research activities somehow related with structured matrices. Some italian groups make their research in collaborations with some international group.

There exists a strong basis made up by a wide and rich literature where most members of this project have given important contributions with a long research tradition on structured matrices dated back to the 80's. In particular, some relevance have the results on the analysis of matrix algebras [BZ], [Bo1], [Bo2], [BDF] together with the more recent results where the Toeplitz matrix technology is applied to the numerical solution of Markov chains and to queueing theory [BM2], [BM3], [BM4], [BMR], [M1], and to solving matrix equations [BM4], [M2]. A research line which has provided many results is the analysis of polynomial computations and structured matrix computations [BP], [B], [G1], [G2], [G3], [BGM], [BGM1]. In particular, the relations between Toeplitz like matrices and the symbolic/numerical manipulation of polynomials and power series.

Considerable achievements have been obtained in the line of the analysis of asymptotic spectral properties related to the analysis of the conditioning of Toeplitz systems and of the design of preconditioners [BF], [BS],[DB], [DB1], [DBS], [S1], [S2], [S3]. A systematic analysis of effective preconditioners for the conjugate gradient iteration has been performed in [DB]. The algebraic multigrid method for Toeplitz matrices has been introduced and analyzed in [FS]. Significant progress in the interplay between preconditioning in matrix algebras and functional approximation have been obtained in [S1]. The analysis of structures provided by elliptic differential operators is performed in [ST]. The analysis of spectral properties of Hankel matrices with applications is performed in [Fa], [Fa1].

An important application of the methodologies related to structured matrices has been developed in [BDB], [BBDB], [DB] and concerns the solution of image restoration problems where the structural properties of the specific physical models are fully exploited in tomography models (SPECT) and in astronomical problems with infrared imaging where inverse problems are treated. Some people of the project have a long tradition and expertise in the field.

The analysis of infinite matrices, spectral factorizations and Banach algebras has had interesting algorithmic achievements [GMRS], [GMRS1], [MRS], with applications to the solution of (perturbed) semi-infinite systems, to the computation of spectral factorization, to the solution of integral equations, to functional approximation problems and to acoustic problems. In particular, the spectral factorization of bi-infinite Toeplitz matrices with scalar/block entries has been studied and necessary and sufficient conditions for its existence have been given in a constructive way. Methods for computing the spectral factorization have been proposed. The existence of a limit profile in the Gram-Schmidt orthonormalization process applied to a sequence of functions generated by shifting their variable, has been proved.

A certain relevance has had the use of structured matrix analysis in unconstrained optimization problems with applications in the optimization of neural networks [DFFZ] and the new methods, based on structured matrices, for solving total least squares problems [LMV].

[B]D.Bini, Using FFT-based techniques in polynomial and matrix computations: recent advances and applications. Numer.Funct.Anal.Optim. 21,2000
[BBDB]D.Bindi, P.Brianzi, F.Di Benedetto, A Fourier approach to the natural pixel discretization of brain single-photon emission computed tomography. Int. J. Imaging Syst. and Technol. 12,2002, 1-8
[BeBo]M.Bertero,P.Boccacci, Introduction to inverse problems in imaging, Institute of Physics Publishing, Bristol, 1998.
[BD]E.Bozzo,C.Di Fiore, On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition. SIAM J. Matrix Anal.Appl. 16,1995
[BDB]P.Brianzi,F.Di Benedetto, Exploiting matrix structures in SPECT models", Structured Matrices: Recent Developments In Theory And Computation, D.Bini, E.Tyrtyshnikov, P.Yalamov Eds., Nova Science Pub.Inc., New York,2001
[BF]D.Bini,P.Favati, On a matrix algebra related to the discrete Hartley transform. SIAM J. Matrix Anal.Appl. 14,1993
[BG1]D.Bini,L.Gemignani, Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation. Lin.Alg.Appl. 284(1998).
[BGM]D.Bini,L.Gemignani,B.Meini, Factorization of analytic functions by means of Koenig's theorem and Toeplitz, computations, Numer. Math. 89,2001.
[BGM1]D.Bini,L.Gemignani,B.Meini, Computations with infinite Toeplitz matrices and polynomials, Lin.Alg.Appl. 343,2002.
[BM1]D.Bini,B.Meini, Effective methods for solving banded Toeplitz systems. SIAM J. Matrix Anal. Appl. 20(1999).
[BM2]D.Bini,B.Meini, Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queueing problems. Lin.Alg.Appl. 272(1998).
[BM3]D.Bini,B.Meini, Improved cyclic reduction for solving queueing problems. Numer.Algo. 15(1997).
[BM4]D.Bini,B.Meini, On the solution of a nonlinear matrix equation arising in queueing problems. SIAM J. Matrix Anal.Appl. 17(1996).
[BMR]D.Bini,B.Meini,V. Ramaswami, Analyzing M/G/1 paradigms through QBDs: the role of the block structure in computing the matrix G, in Adv. in Alg. Methods for Stoch. Models, Proc. G. Latouche and P. Taylor eds., Notable Publications, 2000.
[Bo1]E.Bozzo, Algebras in matrix spaces with displacement structure. Lin.Mult. Alg. 42(1997).
[Bo2]E.Bozzo, Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices. Lin.Alg.Appl.230(1995).
[BP]D.Bini,V.Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston, MA, 1994.
[BS]A.Boettcher,B.Silbermann, Introduction to Large Truncated Toeplitz Matrices, Universitext, Springer, New York 1999.
[BTY]D.Bini,E.Tyrtyshnikov,P.Yalamov, Structured Matrices: Recent Developments in Theory and Computation, Nova Science Inc. N.Y. 2001.
[BvB]A.Bultheel,M.Van Barel, Linear algebra, rational approximation and orthogonal polynomials. North-Holland, Amsterdam, 1997.
[BZ]R.Bevilacqua,P.Zellini, Structure of algebras of commutative matrices. Lin.Alg.Appl. 233(1996).
[CN]R.Chan,M.Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev, 38 1996.
[CPS]R.Chan,D.Potts,G.Steidl, Preconditioners for nondefinite Hermitian Toeplitz systems. SIAM J. Matrix Anal. Appl. 22(2000), 647-665
[DB]F.DiBenedetto, Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM Sci Comp, 16(1995).
[DB1]F.DiBenedetto, Preconditioning of block Toeplitz matrices by sine transform, SIAM SCiComp., 18, 1997.
[DBS]F.DiBenedetto,S.Serra, A unifying approach to abstract matrix algebra preconditioning, Numer. Math. 82(1999).
[DFFZ]C.DiFiore,S.Fanelli,P.Zellini, Matrix algebras in quasi-Newtonian algorithms for optimal learning in multi-layer perceptrons. Proc. ICONIP '99, Dunedin, New Zeeland, 1999.
[Fa]D.Fasino, Spectral properties of Hankel matrices and numerical solution of finite moment problems, J. Comp. App.Math. 65(1995).
[FT]D.Fasino, P. Tilli, Spectral clustering properties of block multilevel Hankel matrices. Lin.Alg.Appl. 306(2000).
[FS]G.Fiorentino,S.Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM Sci Comp, 17,1996.
[G1]L.Gemignani, A hybrid approach to the computation of the inertia of a parametric family of Bezoutians with application to some stability problems for bivariate polynomials. Lin.Alg.Appl. 283(1998).
[G2]L.Gemignani, Computing a factor of a polynomial by means of multishift LR algorithms. SIAM J. Matrix Anal.Appl.19(1998).
[G3]L.Gemignani, Schur complements of Bezoutians and the inversion of block Hankel and block Toeplitz matrices. Lin.Alg.Appl. 253(1997).
[G4]L.Gemignani, Computing a Hurwitz factorization of a polynomial. J. Comput. Appl.Math. 126(2000).
[GGK]I.Gohberg,S.Goldberg,M.Kaashoek. Classes of linear operators. Vol. I, Birkhäuser, Basel, 1990.
[GKO]I.Gohberg,T.Kailath,V.Olshevsky, Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comp. 64(1995).
[GLR]I.Gohberg,P.Lancaster,L.Rodman, Matrix polynomials. Academic Press, Inc. New York, 1982.
[GMRS]T.N.T.Goodman,C.A.Micchelli,G.Rodriguez,S.Seatzu. On the limiting profile arising from orthonormalizing shifts of exponentially decaying functions. IMA J. Num.Anal., 18, 1998.
[GMRS1]T.Goodman,C.Micchelli,G.Rodriguez,S.Seatzu. Spectral factorization of Laurent polynomials. Adv. in Comp.Math.,7,1997.
[GoS]I.Gohberg,A.Semencul, The inversion of finite Toeplitz matricesand their continual analogues. Mat.Issled 7,1972.
[GS]U.Grenander,G.Szego, Toeplitz Forms and their Applications. Univ. of California Press, Berkley 1958.
[H]T.Huckle, Iterative methods for ill-conditioned Toeplitz systems, Calcolo 33,1966
[HK]N.Higham, H-M.Kim, Numerical analysis of quadratic matrix equation, IMA J. Num.An. 20, 2000.
[HR]G.Heinig,K.Rost, Algebraic methods for Toeplitz-like matrices and operators. Birkhäuser, Basel, 1984.
[KS]T.Kailath,A.Sayed Eds., Fast Reliable Methods for Matrices with Structure, SIAM Philadelphia 1999.
[KvB]P.Kravanja,M.Van Barel, Computing the zeros of analytic functions. Lecture Notes in Math., 1727. Springer, Berlin, 2000.
[LMV]P.Lemmerling,N.Mastronardi,S.VanHuffel, Fast algorithm for solving the Hankel/Toeplitz structured total least squares problem, Numer.Algo. 23,2000.
[LR]G.Latouche,V.Ramaswami, Introduction to matrix analytic methods in stochastic modeling. SIAM, Philadelphia, 1999.
[MRS]C.vander Mee,G.Rodriguez,S.Seatzu. Spectral factorization of bi-infinite multi-index block Toeplitz matrices. Lin.Alg.App. 343/344, 2001.
[M1]B.Meini An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stochastic Models, 13,1997.
[M2]B.Meini, Efficient computation of the extreme solutions of X+A^*X^{-1}A=Q and X-A^*X^{-1}A=Q. MathComp 2001.
[Ne]M.Neuts, Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker, Inc., New York, 1989.
[NPPT]J.Nagy,V.Pauca,R.Plemmons,T.Torgersen, Degradation reduction in optics imagery using Toeplitz structure. Calcolo 33,(1996), 269-288
[O]V.Olshevsky Ed., Structured Matrices in Mathematics, Computer Science and Engineering II, Contemp. Math. 281, 2001.
[S1]S.Serra, A Korovkin-type Theory for finite Toeplitz operators via matrix algebras, Num.Math., 82,(1999).
[S2]S.Serra, An ergodic theorem for classes of preconditioned matrices, Lin.Alg. Appl., 282(1998),161-183.
[S3]S.Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Lin.Alg.Appl.,270 1998, 109-129.
[ST]S.Serra,C.Tablino Possio, Spectral and structural analysis of high precision Finite Difference matrices for Elliptic Operators, Linear Alg. Appl., 293(1999), pp. 85-131.
[Str]G.Strang, A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74(1986), 171-176
[Tr]W.Trench, An algorithm for the inversion of finite Toeplitz matrices, J. Soc.Ind.App.Math. 12,1964.
[TZ]E.Tyrtyshnikov,N.Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Lin.Alg.App., 270 1998, 15-27.

Fase 1

Durata:	24 mesi		Costo previsto:	185.600 Euro

Descrizione:

Several collaborations already exist among the different Research Units, throughout denoted as U1,U2,U3. In order to better articulate the research activity in a more organic way and to create synergies, we will form a coordination committee formed by the 3 responsibles of the Research Units. This committee will meet periodically to trace the state of the art of the research, to exchange information about the achievements and to program further meetings among the units.

At the beginning of the project we plan to make an initial meeting of the researchers of all the units in order to coordinate the activity. A workshop is planned after about one year to trace the state of the art of the project. A final workshop is planned at the end where the results obtained in the project are presented. The latter workshop is opened to external researchers, belonging to national and international research groups.
 

A strategic line of the project is to promote the relations between the more applicative aspects (see parts C and D of section 2.1 of this form) and the theoretical issues (part A), by supporting and improving the interactions between the researchers who have more experience in the applications with the ones who have a long expertise in structured numerical linear algebra. This will create synergies and benefits for the whole project. In fact, we expect that, on one hand this strategy will favor the use and the application of theoretical and computational tools to the solution of specific problems with the consequent development of effective software and with the substantial reduction of the computational costs. On the other hand, this strategy will allow the researchers to more deeply investigate specific applicative problems and, consequently, to favor the development of new theoretical and computational tools of general use for structured matrix analysis. This strategy will be implemented by periodically organizing short workshops on very specific subjects of interest which, if needed, will be opened to researchers of international groups who can be invited by the single Research Units. Therefore we plan frequent contacts of researchers of the different units and frequent contacts with researchers of other international research groups to be obtained through short visits.
 

Each Research Unit will provide autonomously to creating prototype software concerning all the algorithms designed and analyzed in the specific program. However, in order to make more significant comparisons and in order that each unit can easily use and improve the software made by other units, in the coordinating meetings we will state the common features which all the different pieces of software must satisfy. We will create a network of fast workstations which constitute the hardware structure where the prototype software made by the different units is kept, tested, elaborated, compared and integrated. This hardware structure will store also the set of test problems which will be constructed in the research activity. The access to the information is opened and is realized by means of web pages. The access to the computers will be managed through accounting.
 

Concerning the costs of the project we planned some specific expenses, having a global or strategic value, for the overall amount of about 46000 euros. They are: two research fellowships for 33000 euros which will strengthen units U1 and U2; the cost of the above mentioned hardware structure accessible to all the units for the cost of about 15000 euros (U1); the contribution of about 8000 euros (U3) for organizing the International Workshop in Operator Theory and Applications, to be held in June 2003.
 

Concerning the research activity, we will pursue the goals reported in section 2.1 of this form, to which we refer the reader for what follows.
 

Concerning part
A- Theoretical issues
The Unit U1 will investigate on matrix algebras of the Hartley kind together with the associated representation (inversion) formulas, and study generalizations to wider classes (A1) with the goal of preparing computational tools for the design of efficient preconditioners with special attention to optimization problems. The research of Unit U1 will also concern the properties of spectral factorizations of semi-infinite (multi-level) Toeplitz matrices with scalar or with block entries and on their relations with operations on Laurent polynomials, in order to obtain new theoretical tools for the design of effective numerical algorithms for polynomial and matrix computations (A5). Properties of the approximate displacement rank will be studied.
Another subject of interest is the analysis of QR factorization of Cauchy matrices with special attention to orthogonalization problems of rational functions(A6).
 

The Unit U2 will analyze theoretical properties of superoptimal preconditioners in matrix algebras (A1), more specifically, monotonicity properties. Here, the aim is to prepare theoretical tools to design effective preconditioners endowed also of regularizing properties. Spectral properties of sequences of Toeplitz matrices will be analized with the aim of extending to the case of multilevel matrices the distributional results and the concept of locally Topelitz matrix (A2). The asymptotic condition number of displacement-structured matrices will be studied in terms of the parameters that characterize it (A3). Besides theoretical analytic issues, this research line aims to create tools for the design of numerical algorithms for structured matrices and to favor synergies between fields like Operator Theory and Asymptotic Linear Algebra (A4). Another subject of interest is the analysis of QR factorization of Cauchy matrices with special attention to orthogonalization problems of rational functions (A6).
 

The Unit U3 will mainly consider the analysis of infinite Toeplitz matrices, more specifically concerning the problem of computing spectral factorizations of Toeplitz matrices in weighted Banach algebras. One goal is to extend to multilevel (block) Toeplitz matrices similar results known for the single level and scalar case by means of an asymptotic analysis of the coefficients of the factorization (A5). Another goal is to create new tools for the design and analysis of fast algorithms for Toeplitz systems which are infinite or have large dimensions, preconditioning techniques included, and to create synergies between Operator Theory and Numerical Linear Algebra (A4). The Unit U3 will also develop the theoretical background together with computational tools for the numerical solution of (perturbed) integral equations in the plane and in the half-space. Here the goal of the theoretical analysis is to extend the methodology introduced for solving infinite systems to integral equations.
 

Concerning the theoretical issues we plan very strict collaborations between U1 and U3 (part A5); U2 and U3 (part A4); U1 and U2 (part A1,A6).
 

Concerning part
B- Algorithmic issues
The Unit U1 is mainly involved in the design and analysis of algorithms for solving infinite (multilevel) Toeplitz systems with scalar/block entries, for computing spectral factorization (B3) and for performing computations with Laurent polynomials with scalar/block coefficients, in particular factoring polynomial and power series (B5), algorithm based on evaluation/interpolation techniques and on Wilson's method. Another related issue is the solution of matrix equation for which new algorithms based on Toeplitz and Laurent computations will be designed (B4). Methods for the QR factorization of structured matrices based on polynomial computations are analyzed (B6). Further research topics are: using the concept of approximate displacement rank for inverting Toeplitz matrices, the design of Toeplitz preconditioners based on factorization of infinite matrices (B1), the analysis of multigrid methods for Toeplitz matrices (B2). The Unit U1 will apply also the results on matrix algebras to the design of new preconditioners for Toeplitz matrices (B1). In particular, the optimal preconditioner by T. Chan will be analyzed by a more general point of view in terms of wider sets of matrices including algebras which are not diagonalized by an orthogonal transform like noncommutative group algebras. The results concerning matrix algebra will be applied also for designing algorithms for nonconstrained minimization problems and total least squares problems.
 

The Unit U2 will apply the results of the theoretical analysis for the design of preconditioners of multilevel Toeplitz matrices, for locally Toeplitz matrices. The same results will be applied for the design of regularizing preconditioners like the superoptimal preconditioner (B1) with strong motivations related to image restoration. The analysis of numerical and computational issues of the multigrid techniques is performed concerning more specifically matrix algebras (B2). Numerical methods for computing the QR decomposition of structured matrices (B6) will be investigated.
 

The Unit 3 will apply the tools of A5 to the analysis of preconditioners for finite (multilevel and block) Toeplitz systems (B1) based on spectral factorizations, to the design and analysis of algorithms for computing spectral factorizations (B3) based on the theory of matrix polynomial and on the band extension technique.
 

Concerning the algorithmic issues we plan collaborations among the three units concerning item B1, and between U1 and U3 concerning item B3; between U1 and U2 concerning B2,B6.
 

Concerning part
C-Applications
The Unit U1 is mainly concerned with the numerical solution of Markov chains which model problems in queueing theory. These problems will be analyzed also with the aim of pointing out in a more clear way the intrinsic structural properties (C4). The same Unit will work on unconstrained optimization problems and on the analysis of neural networks (C6). The research has the main aim of proving "ad hoc" convergence theorems for the learning process on supervised neural networks (multi-layer perceptrons and recurrent networks) and to design new effective algorithms for minimizing the error function. Total Least squares problems will be considered (C6). Problems of rational interpolation will be treated in terms of Cauchy matrices (C5).
 

The Unit U2 will apply the computational tools and the new algorithms to the discrete solution (by means of finite-differences, finite-elements, and collocation methods) of certain partial differential equations (C3). The same tools will be applied to problems of image restoration (C1). The theoretical tools will be applied also to the positive approximation of continuous positive functions and to the numerical quadrature of multivariate functions (C5). The Unit U2 will apply the algorithmic results to the solution of certain image restoration problems (C1) with specific attention to the LBT (Large Binocular Telescope) problem, to the SPECT (Single Photon Emission Computed Tomography) problem, and to the infrared imaging models. These models will be analyzed with also the aim of pointing out in a more clear way the intrinsic structural properties (C4).
 

The Unit U3 will work on applications related to the numerical solution of integral equations and of partial differential equations (C2,C3), in particular to acoustic problems, inverse scattering problems, wave propagation in wave guides, applied geophysics.
 

Concerning applications, there are specific collaborations between Units U1 and U2 concerning item C5. Possible collaborations can arise between Unit 2 and the other two units concerning regularizing preconditioners and imaging problems. Collaboration may also start on minimum problems between U1 and U2.
 

Concerning part
D-Software
All the units are involved for the creation of a set of test problems (D2) and for the preparation of prototype software and numerical validation of algorithms (D1). In particular, the Unit U1 is in charge for creating a web page with the links to all the software and to the test problems (D3), and for creating a software implementation of recursive techniques for polynomial factorization (D4), while the Unit U2 is in charge to create specific software for multigrid methods (D5).
Units involved in each subject:
A1: U1, U2, U3
A2: U2
A3: U2
A4: U2, U3
A5: U1, U3
A6: U1, U2
B1: U1, U2, U3
B2: U1, U2
B3: U1, U3
B4: U1
B5: U1
B6: U1, U2
C1: U2
C2: U3,
C3: U2, U3
C4: U1
C5: U1, U2
C6: U1
D1: U1, U2, U3
D2: U1, U2, U3
D3: U1
D4: U1
D5: U2
Subjects treated by each unit
U1: A1,A2,A6,..........B1,B2,B3,B4,B5,B6,...C4,C5,C6,...D1,D2,D3,D4
U2: A1,A2,A3,A4,A6,....B1,B2,B6,..... ... .C1,C3,C5,...D1,D2,D5
U3: A4,A5,.... .... .... ...B1,B3................C2,C3,......D1,D2

Risultati parziali attesi:

We expect that the theoretical achievements of our research will allow us to obtain very effective computational and algorithmic advances, among which:

Classification of new matrix algebras of Hartley-like type and new inversion formulas. Their use as preconditioners, applications to minimum problems and neural networks.
 

Design of new efficient preconditioners coming either from the analysis of new matrix algebras (A1) or from the asymptotic spectral analysis (A2) with effective applications to the finite-difference solution of elliptic PDEs with arbitrary boundary conditions.
 

Convergence result of the multigrid method applied to matrix algebras, design of efficient multigrid algorithm for bi-circulant matrices and for the cosine algebra.
 

Design of regularizing preconditioners based on superoptimal operators with applications to image restoration problems. Better understanding of superoptimal operators in relation to regularization properties. Better algorithms for the LBT (Large Binocular Telescope) image restoration model.
 

Convergence results for the coefficients of spectral factorizations of semi-infinite multilevel (block) Toeplitz matrices and new asymptotically and effectively fast algorithms for their computation. New asymptotically and effectively fast algorithms for solving finite and infinite (multilevel) Toeplitz systems with scalar/block entries with possible perturbations.
 

Better understanding of the relations between Laurent polynomial computations and Toeplitz matrix computations. New asymptotically and effectively fast algorithms for inverting Laurent polynomials. Better understanding between Laurent polynomial computations and solving polynomial (power series) matrix equations.
 

Better understanding of the problem of polynomial factorization in terms of structured matrix computations, numerical conditioning and convergence.
 

More efficient algorithms in terms of speed and accuracy for the numerical solution of Markov chains modeling queueing problems, with specific attention to recursively defined structures (Tree structures).
 

Among the expected results we include the creation of web pages related to the project with links to the different algorithms and to the set of test problems; the creation of software for recursive factorization of polynomials and for multigrid techniques.

Unita' di ricerca impegnate:
 

Unità nº 1

Unità nº 2

Unità nº 3

The evaluation of the project should be done in terms of the quality of the scientific results obtained. This evaluation can be performed as follows:
1- by looking at the quality of the journals where the main results are published;
2- by looking at the international visibility and dissemination of the results; this can be performed by looking at the number and the relevance of the international conferences where the results are presented.
3- The quality of the algorithmic achievements can be also evaluated in terms of the reduction of the cpu time needed to execute the algorithms and in terms of the numerical performances.
A dynamical monitoring will be performed: as already written in part 2.4, the coordinating committee, formed by the coordinators of the Research Units, will meet periodically. At the end of each meeting, a report on the state of the advancement of the project will be written and inserted in a web page containing all the relevant information of the project.