Main research topics

See Publications of Michela Redivo Zaglia for the bibliographic citations inserted in the text.

I worked on the following topics, some of which having interconnections:

Numerical linear and nonlinear algebra with applications

• Lanczos-type methods form a wide class of methods for solving systems of linear equations. Algorithms for their implementation can suffer from breakdown (division by zero) or near–breakdown (division by a quantity close to zero) thus leading to the impossibility to continue the computations or to an important propagation of rounding errors due to the computer’s arithmetic. This is the case of the BiCG, the CGS or the BiCGSTAB. The problems related to such types of breakdowns have been completely solved in a series of papers using the theory of formal orthogonal polynomials which form the basis of Krylov subspace methods [A1], [A2], [A3], [A5], [A7], [A10], [P9], [P8], [A13], [P10], [A15], [A17]. In this domain, another important problem is to study transpose–free methods. These methods were studied in [A11], [P7]. Block versions were given in [A16].
• An important application of extrapolation methods is the acceleration of iterative methods used in Web search. The most popular algorithm is the PageRank (used by Google), and the power method is the mathematical tool used. But the dimension is huge and the convergence is slow. One possibility for accelerating this process is to use extrapolation methods, also on parallel computers. Such procedures can be applied also to the computation of eigenvectors of irreducible stochastic matrices. See [A21], [A22], [A23], [A24], [P12], [P11].
• A well known technique for solving an ill-conditioned linear system is Tikhonov 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 1998, we computed the regularized solutions for several values of the regularization parameter and then we extrapolated at zero. The numerical results obtained prove the effectiveness of this innovative technique [A12]. A first attempt for extending this technique to the multiparameter case (that allows to add simultaneously several regularization terms) was proposed in 2003 [A18]. Again together with the Cagliari group of research, following the work published in 1998, we recently investigated the possibility to use the TSVD method which allows one to replace the ill-conditioned matrix A with a well-conditioned low-rank matrix obtained by keeping the first k singular triplets of its Singular Value Decomposition. We try to find a method. based on an extrapolation procedure, to identify the regularization parameter k when the TSVD and the TGSVD are used as regularization methods [IP6].
• In 2018, we published a paper [A32] where a general framework for extrapolation of vector, matrix, and tensor sequences by Shanks transformation, and for the related fixed point methods (including the MMPE, the MPE, the RRE, the various TEAs, Pulay Mixing and Anderson Acceleration) is presented. This paper appeared in SIAM Review, a quite prestigious journal.
• Motivated by the improvement given by extrapolation methods in the computation of the PageRank vector, we proposed and investigated the use of these techniques also for the particular setting of tensor Z-eigenpairs problems arising from the analysis of the multilinear PageRank. We showed that extrapolation for the computation of the multilinear PageRank using fixed-point iterations improves substantially the efficiency and effectiveness on the test problems (also on real-world datasets of large dimension) we considered at a limited additional cost [A37]. Moreover, we obtain interesting results also for shifted and extrapolated power sequences for tensor ℓ^p-eigenpairs [A38]. Other applications to complex networks are in progress.
• In [A32], the relationships between Shanks transformation and already well known and previously used convergence acceleration methods were defined (the topological ε-algorithm (TEA), the Modified Minimal Polynomial Extrapolation (MMPE) method, the Minimal method Polynomial Extrapolation (MPE) and the Reduced Rank Extrapolation (RRE) method). All these methods can also be used for solving vector, matrix or tensor nonlinear equations, and provide quadratic convergence. The case of Anderson acceleration (AA), a method widely used in physics and chemistry, for the search of fixed points of non-linear applications, has also been treated and the general framework of the coupled transformations thus defined. But many other variations of Anderson’s method were defined in the article that can be used. Such variants are the subject of the article [SU1], which was submitted for publication in July 2020. The article defines a general framework that includes most of the known acceleration strategies, also considering the Anderson acceleration algorithm, in a new light and exploiting a connection with Quasi-Newton methods, in order to establish local linear convergence results of Anderson-type techniques. The methods are tested on a number of problems, including some that derive from nonlinear partial differential equations.
• On the occasion of a visit to Padua by Dr. Stefano Pozza in January 2020, he carried out a seminar entitled “A Lanczos-like method for the time-ordered exponential”. After this seminar, the idea of a Lanczos-type method for tensors arose. Together with Stefano Cipolla, having thoroughly investigated the literature and given the fact that it would have been a new topic, not yet adequately developed, we have already laid the theoretical and algorithmic foundations as well as an idea of how to deal with the so-called “breakdown” that can be present with the algorithms in the matrix case and which was successfully completely solved years ago by the undersigned. The natural block structure of several linear algebra problem, suggests us the introduction of a tensorization of the problem, and the use of a modified Block-Lanczos procedure, which is the subject of this work. In particular we studied how the classic Krylov-type results can be written in a tensor-like fashion. The related work [IP3] is in an advanced stage of drafting.
• A book treating all aspects of the History of Numerical Linear Algebra (elimination methods, determinants, factorization and iterative methods, matrix properties, computer implementation, and software) is in preparation, coauthored with C. Brezinski and G. Meurant (already written more than 700 pages). The second part of the book gathered the biographies of the main contributors. An extensive bibliography, already over 1800 references, will end the book [IP1].

Other topics on which I worked are

• Construction of hybrid procedures for solving linear systems [A4].
• The reverse bordering method [A6].
• Study of the numerical stability of Lanczos’ tridiagonalization [A14].
• Construction of block projection methods for linear systems [A16].
• Pseudo-Schur complements and their properties [A20].
• A rational Arnoldi procedure for ill-conditioned linear systems [A26].
• Preconditioners of linear systems via matrix function evaluation [A28].
• Methods for accelerating the convergence of Kaczmarz’s method [A30].

Approximation theory and numerical approximation

Extrapolation methods

In several scientific domains, one has often to deal with sequences and series, that converge slowly and it is a serious drawback to their effective use. Extrapolation methods form the basis of new methods for solving such problems. They also have several specific applications. Extrapolation methods form now an explicit area of numerical analysis having connections with many other important topics (Padé approximation, projection methods, ...). Besides convergence acceleration of (scalar, vector, matrix or tensor) sequences, they can also furnish new solution methods for different problems. In the past, particular attention was given to new approaches for deepening our knowledge about known sequence transformations and obtaining new ones, in particular in the vector and matrix cases. Useful tools that lead to new vector sequence transformations have been the Schur complement and its extension to rectangular matrices, and some determinantal properties like the Sylvester determinantal identity. Recursive algorithms have been obtained and programmed with great care. We also obtained theoretical results on convergence and acceleration.

My researches in this domain include the methodology of sequence transformations, theoretical results on existing algorithms, new algorithms, and applications to the solution of various numerical analysis problems.

• In 1991, with my colleague C. Brezinski, considered worldwide one of the maximum experts of this field of research, we published a book on the subject and a software library, see [L1]. This still appears to be the main reference text, together with very few others, of researchers interested in extrapolation and acceleration of the convergence of sequences, and it is widely cited.
• About thirty years after the monograph [L1], taking into account the extensive research and the new results subsequently published by numerous authors, it was felt the need to write a new monograph that would cover all aspects, even the most recent and innovative, of this broad class of transformations: theory, algorithms, applications and software. The pandemic situation, with the obligatory stay in Padua during my sabbatical year, allows us to complete this ambitious project, which has developed well beyond the treatment of extrapolation methods, producing a monograph of over 400 pages, which has been published by Springer Nature in 2020 [L2]. This book paints a fresco of the field of extrapolation and rational approximation over the last several centuries to the present through the works of their primary contributors. It can serve as an introduction to the topics covered, including extrapolation methods, Padé approximation, orthogonal polynomials, continued fractions, Lanczos-type methods, etc.; it also provides in depth discussion of the many links between these subjects. A highlight of this book is the presentation of the human side of the fields discussed via personal testimonies from contemporary researchers, their anecdotes, and their exclusive remembrances of some of the “actors”. This book shows how research in this domain started and evolved. Biographies of other scholars encountered have also been included. An important branch of mathematics is described in its historical context, opening the way to new developments. After a mathematical introduction, the book contains a precise description of the mathematical landscape of these fields spanning from the 19th century to the first part of the 20th. After an analysis of the works produced after that period (in particular those of Richardson, Aitken, Shanks, Wynn, and others), the most recent developments and applications are reviewed.
• Peter Wynn, the researcher that discovered the (scalar, vector and Matrix) ε-algorithms, that are very well known extrapolation methods, implementing and generalizing the Shanks transformation, died December 2017. After his death, many unpublished handwritten documents he left at the house of friends of him came to light. After the publication, in January 2019, of an issue of the journal Numerical Algorithms, entirely dedicated to Peter Wynn, C. Brezinski and me, we were contacted by F. Alexander Norman, a colleague of these friends, in January 2020. He informed them of the existence of these documents. This is how Wynn’s legacy came to light. They concern orthogonal polynomials, extrapolation methods, Padé approximation, continued fractions, moment problems, Thiele and rational interpolation, complex analysis, series, software, analysis and abstract algebra. A real treasure. Thinking that these manuscripts would have represented valuable additions to the literature on the topics treated, and that they could not be left unknown, since they contain ideas that were never exploited, we analyzed all these documents in a paper now still submitted [SU2]. A B.S. thesis, that aims also to build a site dedicated to the Legacy of Wynn, under my supervision is in progress.
• The vector ε-algorithm, proposed by P. Wynn (1962) is, in the real applications, one of the best extrapolation methods. When studying a sequence transformation or an acceleration algorithm, an important notion is that of its kernel (the set of sequences for which the sequence transformation returns the exact limit of the original sequence). Previous theoretical research has shown that the kernel of the vector ε-algorithm contains the kernel of the vector Shanks transformation. But thanks to the works of Ahmed Salam, it is known that this kernels must also contain other sequences (whose expression or characteristics are unknown). It is therefore fundamental to understand the reasons for this manifest superiority but it is not at all evident in the general case. This has been one of the unsolved problems for decades. We then started working with the values of column 2 of the vector ε-algorithm, which corresponds to Aitken’s Δ². We worked on the core of the first step and tried to find which are the sequences of vectors that transform in a constant sequence. This work involves Clifford’s algebra and we were able to express these vectors using the product in this algebra. We still had to fully explain the form of these vectors, linking the theory to rotations and rotors. This is a work in progress [IP4].

I worked on

• A methodology for the construction of extrapolation processes [A40].
• Particular rules for improving the numerical stability of the Θ-algorithm [A41].
• A survey on extrapolation methods [A43].
• A new interpretation of the mechanism of the E–algorithm [A44].
• A study of the kernel of sequence transformations [A45].
• A look–ahead strategy for the implementation of extrapolation methods [A8].
• Construction of new vector and matrix sequence transformations based on biorthogonality [A9].
• A Schur complement approach to the E–algorithm [A19].
• New vector sequence transformations based on the Schur complement [A46].
• Generalizations of Aitken’s Δ² process [A47].
• A review of vector convergence acceleration methods, with applications to linear algebra problems [A25].
• Extended procedures for extrapolation to the limit [A48].
• Extensions of Drummond’s acceleration process [A49].
• A new extension of Shanks’ transformation and a multistep ε-algorithm [A50].
• Extension of Shanks transformation for vector and matrix functions. Application to integrable systems [A58].

More recently

• We coined simplified forms for the topological ε-algorithms [A29]. They also allowed us to obtain convergence and acceleration results for this transformations. We published the corresponding software, and gave applications to fixed point problems and to the computation of matrix functions [A31].
• We showed that extrapolation methods can be quite effective in the numerical solution of Fredholm integral equations [A35].
• We wrote a long paper [A33] (87 pages) describing the genesis and the historical development of Aitken’s process, Shanks transformation, the ε–algorithm, Pulay mixing and Anderson acceleration. It also contains new theoretical results and testimonies by many actors of the field.
• We introduced Shanks transformations for sequences of rectangular matrices [A34], and we showed that the square matrix ε–algorithm implements them.
• We found a new procedure for connecting the scalar ε–algorithm to Shanks transformation, and vice–versa [A53].

Rational interpolation and approximation

In rational approximation we worked on a new idea. In Padé–type approximants, the denominators can be arbitrarily chosen. These approximants match the original series up to a certain degree, but they do not possess an interpolation property. In the barycentric formula for rational interpolants, the weights can be arbitrarily chosen but they don’t have an approximation property. In both cases, we used these degrees of freedom so that the Padé–type approximants also possess an interpolation property, and that the barycentic interpolants match the series expansion of the function as far as possible [A51]. The computation of Padé approximants poses numerical stability problems. This is a well known situation for polynomial interpolation. In this case, a barycentric formula is preferable. Thus, standard Padé approximants have been written under a barycentric form with free parameters, thus allowing to better control their numerical stability [A52].

Special functions

Biorthogonality and formal orthogonal polynomial form a central theme in several of my research topics.

The notion of biorthogonality is a very general one having applications in many branches of numerical analysis. For example, it leads, on one hand, to formal biorthogonal polynomials and, on the other hand, to the method of moments of Vorobyev.

Formal orthogonal polynomials have been studied for many years now, and they play a crucial role in various important numerical methods and applications. They open the way to the concepts of formal vector and scalar orthogonality which form a natural basis for the study of vector and scalar Padé approximants, continued fractions, rational interpolation, Gaussian quadratures and the Kronrod procedure for estimating its error, Krylov subspace methods for solving systems of linear equations, and extrapolation methods for scalar and vector sequences. The concept has been extended to matrix orthogonality which is used for block systems of linear equations. Methods for the iterative solution of systems of nonlinear equations also benefit from this approach.

The method of moments leads to Galerkin method and to projection methods for linear equations, and to the solution of the matrix eigenvalue problem (Lanczos-type methods). Some convergence acceleration methods recently used in the Google’s PageRank problem for web search have also been put into this framework.

An important role in the theory of biorthogonality is played by ratios of determinants, recursive computational rules, and the notion of Schur complement which have been extensively studied.

A notion closely related to biorthogonality is the so called “quasi-orthogonality”. Quasi-orthogonal polynomials are a particular case of orthogonal polynomials and some of their properties were studied in the univariate case, for determining the locations of their zeros and the measure of orthogonality (a work initiated by Marcel Riesz). They have applications in Gauss-Radau and Gauss-Lobatto quadrature formulae. In [A57] we presented a study of the interlacing properties of some families of classical quasi–orthogonal polynomials. This paper is well cited by the community. A particular case, not included in it, is developed in [A59].

My researches on this topic, apart the works already indicated, include the following subjects

• A new presentation of orthogonal polynomials with application to their computation [A54].
• Study of the orthogonal polynomials of dimension -1 in the non-definite case [A55].
• A procedure for avoiding breakdowns in the computation of orthogonal polynomials [P6].
• The zeros of polynomials satisfying some non standard orthogonality conditions have been studied in [A56].
• A new recursive algorithm for a gaussian quadrature formula via orthogonal polynomials [P2].

Numerical Software

Thanks to my double competence in Computer Science and Numerical Analysis, I was invited, from May 1990, to become a member of the editorial board of the international journal Numerical Algorithms as Software editor. This task concerns the validation of the software submitted to the journal, in controlling its portability, and in checking that it is easy to use for non expert users. The software is validated and, after its acceptation, it is freely distributed through netlib, one of the most known international digital libraries for software.

I developed several software packages that were distributed to the community in different ways.

We remind, in particular, the software library, written in FORTRAN 77, that allows to implement most of the extrapolation algorithms described in [L1] (and that is provided on magnetic media together with the book itself and that can also be freely available through the link
http://www.math.unipd.it/michela/extracode/Extrapolation_Library.html.

Concerning the field of Numerical Linear Algebra, for treating problems of breakdown and near–breakdown in Krylov subspace methods, we inserted, in the public domain netlib library, the packages na1, na5, na8 related to the papers [A1], [A2], [A3], [A5].

An object oriented specialized Matlab toolbox has also been realized. It is named SMT (Structured Matrices Toolbox), and allows the treatment of structured matrices in a natural way, by using the arithmetical operations implemented through fast algorithms. The package has been completed with a test matrices set and with the most common preconditioners. Particular attention was given 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 [A27]. This toolbox was inserted in the netlib library as na30.

For helping the users that wish to try the extrapolation methods, but want to use the Matlab environment, we implemented with this language some of the recursive algorithms for the topological Shanks transformations. In particular, Wynn ε-algorithm with its particular rules able to avoid numerical instability, and the topological ε-algorithms in their original versions and also in their very recent simplified forms have been implemented [A29], [A31]. These simplified algorithms have only one recursive rule instead of two (and, the rule involves only terms with an even index), they required less storage than the initial algorithms, elements of the dual vector space no longer have to be used in the recursive rules but only in their initializations (thus allowing to treat the matrix and the tensor cases), and the numerical stability is improved. A toolbox named EPSfun was built, the corresponding paper has been published A31], and the related software has been inserted in netlib as the package na44. Actually, a version in Python is under construction together with S. Cipolla.

Recently, a package named Extrapolation for nonlinear Fredholm integral equations, in connection with the paper [A35], has been inserted in the public domain Matlab File Exchange site,
https://mathworks.com/matlabcentral/fileexchange/
65048-extrapolation-for-nonlinear-fredholm-integral-equations.

Miscellanea

In the first period of my academic research, until 1989, my interest was focused on issues closer to Computer Science, but, however, I worked with the idea of using them for other applications.

The examination of various types of graphical representations leaded to programs of general use [V2]. Moreover I have deepened the understanding of the control of quality of software and its portability in non-homogeneous environments hardware/software.

In the field of automatic cartography, we founded the way for performing boolean operations between regions (union, intersection and difference), starting from the knowledge of their contours [V4], [V5]. Still in the field of cartography, but with a more focused vision in the development of mathematical models, we built a model, called MOMID, for the analysis of a catchment drainage [P1].

Several books and reports have been published [L5] [L6] [L7] [L3] [L4] [L8] [V1] [V3] [V7]. One of them is on the UNIX operating system and is one of the first books on this topic published in Italy. We also wrote a paper giving a short history of continued fractions [A64] (translated into Greek by M. Mitrouli).

Several didactic review papers for a French encyclopedia which is widely distributed among engineers and engineering high schools were written [P13] [P14].

Updated April 19, 2021