Matrix structures and applications

Bini, Dario A.

Journées Nationales de Calcul Formel. 3 – 7 Novembre 2014, Les cours du CIRM, no. 1 (2014), Exposé no. 1, 45 p.

[1] A. H. Al-Mohy and N. J. Higham. The complex step approximation to the Fréchet derivative of a matrix function. Numer. Algorithms, 53:113–148 (2010). | DOI | Zbl

[2] A. Amiraslani, R. M. Corless, and P. Lancaster. Linearization of matrix polynomials expressed in polynomial bases. IMA J. Numer. Anal., 29(1):141–157, 2009. | DOI | MR | Zbl

[3] G.S. Ammar and W.B. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9, 61–76 (1988). | DOI | MR | Zbl

[4] J.L. Aurentz, T. Mach, R. Vandebril, D.S. Watkins, Fast and backward stable computation of roots of polynomials, TW654, 36 pages, Department of Computer Science, KU Leuven, Leuven, Belgium, August 2014 | Zbl

[5] J.L. Aurentz, R. Vandebril, D.S. Watkins, Fast computation of eigenvalues of companion, comrade, and related matrices, BIT Numer Math 54, 7–30 (2014). | DOI | MR | Zbl

[6] F. Avram, On bilinear forms on Gaussian random variables and Toeplitz matrices, Probab. Theory Related Fields 79, 37–45 (1988). | DOI | MR | Zbl

[7] O. Axelsson and G. Lindskög, On the rate of convergence of the preconditioned conjugate gradient method, Numerische Mathematik, 48, 499–523, 1986. | DOI | MR | Zbl

[8] S. Barnett, A companion matrix analogue for orthogonal polynomials, Linear Algebra Appl., 12, 197–202 (1975). | DOI | MR | Zbl

[9] T. Betcke, N.J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur. NLEVP: A collection of nonlinear eigenvalue problems. http://www.mims.manchester.ac.uk/research/numerical-analysis/nlevp.html. | DOI | Zbl

[10] D. Bini. Parallel solution of certain Toeplitz linear systems. SIAM J. Comput., 13, 268–276 (1984). | DOI | MR | Zbl

[11] D. Bini, M. Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl. 52/53, 99–126 (1983). | DOI | MR | Zbl

[12] D.A. Bini, Y. Eidelman, L. Gemignani, I. Gohberg, Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices SIAM J. Matrix Anal. Appl., 29, 566–585 (2007). | DOI | MR | Zbl

[13] D. Bini, P. Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14, 500–507 (1993). | DOI | MR | Zbl

[14] D.A. Bini, G. Fiorentino, Design, Analysis and Implementation of a Multiprecision Polynomial Rootfinder, Numer. Algorithms, 23, 127–219 (2000). | DOI | Zbl

[15] D.A. Bini, B. Iannazzo, B. Meini, Numerical Solution of Algebraic Riccati Equations, Fundamentals of Algorithms, SIAM, Philadelphia 2012. | DOI | Zbl

[16] D. A. Bini, S. Dendievel, G. Latouche, and B. Meini. Computing the Exponential of Large Block-Triangular Block-Toeplitz Matrices Encountered in Fluid Queues, Linear Algebra Appl., in Press, doi:10.1016/j.laa.2015.03.035. | DOI | MR | Zbl

[17] D. A. Bini, G. Latouche, and B. Meini. Numerical methods for structured Markov chains. Numerical Mathematics and Scientific Computation. Oxford University Press, New York, 2005. Oxford Science Publications. | DOI | Zbl

[18] D.A. Bini, B. Meini, The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond, Numerical Algorithms, 51, 23–60 (2009). | DOI | Zbl

[19] D. A. Bini, V. Noferini, and M. Sharify. Locating the eigenvalues of matrix polynomials. SIAM J. Matrix Anal. Appl., 34, 1708–1727 (2013). | DOI | MR | Zbl

[20] D. Bini and V. Pan. Polynomial and Matrix Computations. Birkhäuser, 1994. | DOI | Zbl

[21] D.A. Bini, L. Robol, Solving secular and polynomial equations: A multiprecision algorithm. J. Comput. Appl. Math., 272, 276–292 (2014). | DOI | MR | Zbl

[22] D.A. Bini, L. Robol, On a class of matrix pencils and $\ell$-ifications equivalent to a given matrix polynomial. Linear Algebra Appl., in Press, doi:10.1016/j.laa.2015.07.017, arXiv:1406.1025 (2014). | DOI | MR

[23] R.R. Bitmead, B.D.O. Anderson, Asymptotically fast solution of Toeplitz and related systems of linear equations. Linear Algebra Appl., 34, 103–116 (1980). | DOI | MR | Zbl

[24] P. Boito, Y. Eidelman, L. Gemignani, Implicit QR for Rank-Structured Matrix Pencils, BIT Numerical Mathematics 54, 85–111 (2014). | DOI | MR | Zbl

[25] P. Boito, Y. Eidelman, L. Gemignani, I. Gohberg, Implicit QR with Compression, Indag. Math. 23, 733–761 (2012). | DOI | MR | Zbl

[26] A. Böttcher, S.M. Grudsky, Toeplitz Matrices, Asymptotic Linear Algebra and Functional Analysis. Text and Readings in Mathematics 18, Hindustan Book Agency, New Delhi 2000. | Zbl

[27] A. Böttcher, B. Silbermann, Introduction to Large Truncated Toeplitz Matrices, Springer, New York 1999. | DOI | MR | Zbl

[28] A. Böttcher, I. Spitkovsky, The factorization problem: Some known results and open questions, Operator Theory: Advances and App., 229, 101–122 (013). | DOI | Zbl

[29] S. Chandrasekaran, M. Gu, J. Xia, J. Zhu, A fast QR algorithm for companion matrices, Recent Advances in Matrix and Operator Theory, Oper. Theory Adv. Appl., vol. 179, Birkhüser, Basel (2008). | DOI | Zbl

[30] R. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10, 542–550 (1989). | DOI | MR | Zbl

[31] R. H.-F. Chan and X.-Q. Jin. An introduction to iterative Toeplitz solvers, volume 5 of Fundamentals of Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2007. | DOI | Zbl

[32] T. F. Chan. An optimal circulant preconditioner for Toeplitz systems. SIAM J. Sci. Statist. Comput., 9(4):766–771, 1988. | DOI | MR | Zbl

[33] R. Chan, G. Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10, 104–119 (1989). | DOI | MR | Zbl

[34] R.M. Corless. Generalized companion matrices in the Lagrange basis. In L. Gonzalez-Vega and T. Recio, editors, Proceedings EACA, June 2004.

[35] R.M. Corless and G. Litt, Generalized Companion Matrices for Polynomials not expressed in Monomial Bases, Ontario Research Centre for Computer Algebra, Department of Applied Mathematics University of Western Ontario http://www.apmaths.uwo.ca/~rcorless/frames/PAPERS/PABV/CMP.pdf.

[36] F. De Terán, F.M. Dopico, J. Pérez, Backward stability of polynomial root-finding using Fiedler companion matrices, IMA J. Numer. Anal. (2014). | DOI | MR | Zbl

[37] F. De Terán, F.M. Dopico, D.S. Mackey, Fiedler companion linearizations, for rectangular matrix polynomials. Linear Algebra Appl., 437, 957–991 (2012). | DOI | MR | Zbl

[38] S. Delvaux, M. Van Barel, A Hessenberg reduction algorithm for rank structured matrices, SIAM J. on Matrix Analysis and App., 29, 895–926 (2007). | DOI | MR | Zbl

[39] F. Di Benedetto, Gram matrices of fast algebras have a rank structure, SIAM J. Matrix Anal. Appl. 31, 526–545 (2009). | DOI | MR | Zbl

[40] Y. Eidelman, L. Gemignani, and I. Gohberg. Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations. Numer. Algorithms, 47, 253–273 (2008). | DOI | MR | Zbl

[41] Y. Eidelman, I. Gohberg, and I. Haimovici. Separable type representations of matrices and fast algorithms. Vol. 1, volume 234 of Operator Theory: Advances and Applications. Birkhäuser/Springer, Basel, 2014. Basics. Completion problems. Multiplication and inversion algorithms. | DOI | Zbl

[42] Y. Eidelman, I. Gohberg, and I. Haimovici. Separable type representations of matrices and fast algorithms. Vol. 2, volume 235 of Operator Theory: Advances and Applications. Birkhäuser/Springer Basel AG, Basel, 2014. Eigenvalue method. | Zbl

[43] M. Fiedler, A note on companion matrices. Linear Algebra and Its Applications, 372:325–331, 2003. | DOI | MR | Zbl

[44] K. Frederix, S. Delvaux, M. Van Barel, An algorithm for computing the eigenvalues of block companion matrices, Numerical Algorithms, volume 62, 261–287 (2013). | DOI | MR | Zbl

[45] F.R. Gantmacher, M.G. Krein, Sur les matrices complètement non négatives et oscillatoires. Compositio Mathematica 4, 445–476 (1937). | Zbl

[46] S. Gaubert and M. Sharify, Tropical scaling of polynomial matrices. In Positive systems, volume 389 of Lecture Notes in Control and Inform. Sci., 291–303. Springer, Berlin, 2009. | DOI

[47] I. Gohberg, T. Kailath, V. Olshevsky (1995). “Fast Gaussian elimination with partial pivoting for matrices with displacement structure”. Mathematics of Computation 64 (212): 1557–1576. | DOI | MR | Zbl

[48] I. Gohberg, P. Lancaster, and L. Rodman. Matrix polynomials. Academic Press Inc., New York, 1982. Computer Science and Applied Mathematics. | Zbl

[49] I. Gohberg and A. Semencul, On the inversion of finite Toeplitz matrices and their continuous analogs (in Russian), Mat. Issled 7, 201–223 (1972). | Zbl

[50] G.H. Golub, Some modified matrix eigenvalue problems, SIAM Review, 15, 318–334 (1973). | DOI | MR | Zbl

[51] I.J. Good, The colleague matrix, a Chebyshev analogue of the companion matrix Quart. J. Math., Oxf. Ser., 12, 61–68 (1961). | DOI | MR | Zbl

[52] T.NT Goodman, C. A. Micchelli, G. Rodriguez, S. Seatzu, Spectral factorization of Laurent polynomials, Advances in Computational Mathematics, 7 429–454 (1997). | DOI | Zbl

[53] U. Grenander, G. Szegő. Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. | Zbl

[54] N. J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. | DOI | Zbl

[55] T. Kailath, A H. Sayed, Displacement Structure: theory and applications, SIAM Review, 297–386, 1995. | DOI | MR | Zbl

[56] T. Kailath and A. H. Sayed, eds., Fast Reliable Algorithms for Matrices with Structure, SIAM Press, 1999. | DOI | Zbl

[57] T. Kailath, S. Y. Kung and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Appl. 68, 395-407 (1979). | DOI | MR | Zbl

[58] F.-R. Lin, W.-K. Ching, M.K. Ng, Fast inversion of triangular Toeplitz matrices, Theoretical Computer Science, 315, 511–523 (2004). | DOI | MR | Zbl

[59] M.F. Neuts. Structured stochastic matrices of $M/G/1$ type and their applications, volume 5 of Probability: Pure and Applied. Marcel Dekker, Inc., New York, 1989. | Zbl

[60] M.F. Neuts. Matrix-geometric solutions in stochastic models. Dover Publications, Inc., New York, 1994. An algorithmic approach, Corrected reprint of the 1981 original.

[61] A. Ostrowski, Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent. Chapitres III et IV. Acta Math. 72, 157–257 (1940) | DOI | Zbl

[62] A. Ostrowski, Addition à notre mémoire: ”Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent.” Acta Math. 75, 183–186 (1943) | DOI | Zbl

[63] S.V. Parter, Extreme eigenvalues of Toeplitz forms and applications to elliptic difference equations, Trans. Amer. Math. Soc., 99 (1966), pp. 153–192. | DOI | MR | Zbl

[64] M.A. Pellet. Sur un mode de séparation des racines des équations et la formule de Lagrange. Bull. Sci. Math., 5:393–395, 1881. | Zbl

[65] F. Poloni, A note on the $O\left(n\right)$-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices, Numer. Algorithms, 55, 115–139 (2010). | DOI | MR | Zbl

[66] Y. Saad, Iterative methods for sparse linear systems, second Edition, SIAM, Philadelphia 2003. | DOI | Zbl

[67] S. Serra Capizzano, Toeplitz matrices: spectral properties and preconditioning in the CG method, NLA courses at FMB in Uppsala, TR 23 (2014), Information Technology Dept, Uppsala University.

[68] S. Serra Capizzano, Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matrix Anal. Appl., 17, 1007–1019 (1996). | DOI | MR | Zbl

[69] S. Serra Capizzano. Optimal, quasi–optimal and superlinear preconditioners for asymptotically ill–conditioned positive definite Toeplitz systems, Math. Comput. 66, 651–665 (1997). | DOI | MR | Zbl

[70] S. Serra Capizzano, E. Tyrtyshnikov, How to prove that a preconditioner cannot be superlinear, Math. Comput. 1305-1316, (2003). | DOI | MR | Zbl

[71] B.T. Smith, Error bounds for zeros of a polynomial based upon Gerschgorin’s theorems, J. Assoc. Comput. Math. 17, 661–674 (1970). | DOI | MR | Zbl

[72] G. Strang, A proposal for Toeplitz matrix calculation, Stnd. Appl. Math. 74, 171–176 (1986). | DOI | Zbl

[73] W.F. Trench, An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl. Math. 12, 515–522 (1964). | DOI | MR

[74] E.E. Tyrtyshnikov, A Unifying Approach to Some Old and New Theorems on Distribution and Clustering, Linear Algebra Appl., 232 1–43 (1996). | DOI | MR | Zbl

[75] E.E. Tyrtyshnikov, N. Zamarashkin. Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl., 270, 15–27 (1998). | DOI | MR | Zbl

[76] M. Van Barel, R. Vandebril, P. Van Dooren, K.  Frederix, Implicit double shift QR-algorithm for companion matrices, Numerische Mathematik, 116, 177–212 (2010). | DOI | MR | Zbl

[77] R. Vandebril and G.M. Del Corso. An implicit multishift qr-algorithm for hermitian plus low rank matrices. SIAM Journal on Scientific Computing, 32, 2190–2212 (2010). | DOI | MR | Zbl

[78] R. Vandebril, M. Van Barel, G. Golub, N. Mastronardi, A bibliography on semiseparable matrices, Calcolo 42, 249–270 (2005) | DOI | MR | Zbl

[79] R. Vandebril, M. Van Barel, N. Mastronardi, Matrix Computations and Semiseparable Matrices, Vol. 1 Linear Systems. Johns Hopkins, Baltimore, Maryland, 2008. | Zbl

[80] R. Vandebril, M. Van Barel, N. Mastronardi, Matrix Computations and Semiseparable Matrices, Vol. 2 Eigenvalue and Singular Value Methods. Johns Hopkins, Baltimore, Maryland, 2008. | Zbl

[81] J. Xia, Y. Xi, M. Gu, A superfast structured solver for toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl., 33, 837–858 (2012). | DOI | MR | Zbl

[82] W. Werner,A generalized companion matrix of a polynomial and some applications, Linear Algebra Appl., 55, 19–36 (1983). | DOI | MR | Zbl

[83] P. Zhlobich, Differential qd algorithm with shifts for rank-structured matrices. SIAM J. Matrix Anal. Appl. 33, 1153–1171 (2012). | DOI | MR | Zbl

[84] S. Zohar, Toeplitz matrix inversion: The algorithm of W.F. Trench, J. Assoc. Comput. Mach. 16, 592–601 (1967). | DOI | Zbl