Matrix structures and applications

Dario A. Bini[1]

  • [1] Dipartimento di Matematica, Università di Pisa, Italy

Les cours du CIRM (2014)

  • Volume: 4, Issue: 1, page 1-45
  • ISSN: 2108-7164

How to cite


Bini, Dario A.. "Matrix structures and applications." Les cours du CIRM 4.1 (2014): 1-45. <>.

affiliation = {Dipartimento di Matematica, Università di Pisa, Italy},
author = {Bini, Dario A.},
journal = {Les cours du CIRM},
language = {eng},
number = {1},
pages = {1-45},
publisher = {CIRM},
title = {Matrix structures and applications},
url = {},
volume = {4},
year = {2014},

AU - Bini, Dario A.
TI - Matrix structures and applications
JO - Les cours du CIRM
PY - 2014
VL - 4
IS - 1
SP - 1
EP - 45
LA - eng
UR -
ER -


  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). Zbl1188.65054MR2566131
  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. Zbl1158.15022MR2470944
  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). Zbl0658.65022MR938136
  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 Zbl1319.65034MR3366913
  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). Zbl1293.65052MR3177953
  6. F. Avram, On bilinear forms on Gaussian random variables and Toeplitz matrices, Probab. Theory Related Fields 79, 37–45 (1988). Zbl0648.60043MR952991
  7. O. Axelsson and G. Lindskög, On the rate of convergence of the preconditioned conjugate gradient method, Numerische Mathematik, 48, 499–523, 1986. Zbl0564.65017MR839614
  8. S. Barnett, A companion matrix analogue for orthogonal polynomials, Linear Algebra Appl., 12, 197–202 (1975). Zbl0327.15026MR387310
  9. T. Betcke, N.J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur. NLEVP: A collection of nonlinear eigenvalue problems. Zbl1295.65140
  10. D. Bini. Parallel solution of certain Toeplitz linear systems. SIAM J. Comput., 13, 268–276 (1984). Zbl0534.68026MR739989
  11. D. Bini, M. Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl. 52/53, 99–126 (1983). Zbl0549.15005MR709346
  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). Zbl1147.65031MR2318363
  13. D. Bini, P. Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14, 500–507 (1993). Zbl0773.65029MR1211803
  14. D.A. Bini, G. Fiorentino, Design, Analysis and Implementation of a Multiprecision Polynomial Rootfinder, Numer. Algorithms, 23, 127–219 (2000). Zbl1018.65061MR1772050
  15. D.A. Bini, B. Iannazzo, B. Meini, Numerical Solution of Algebraic Riccati Equations, Fundamentals of Algorithms, SIAM, Philadelphia 2012. Zbl1244.65058MR2896454
  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. Zbl06579448
  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. Zbl1076.60002MR2132031
  18. D.A. Bini, B. Meini, The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond, Numerical Algorithms, 51, 23–60 (2009). Zbl1170.65021MR2505832
  19. D. A. Bini, V. Noferini, and M. Sharify. Locating the eigenvalues of matrix polynomials. SIAM J. Matrix Anal. Appl., 34, 1708–1727 (2013). Zbl1291.15048MR3144796
  20. D. Bini and V. Pan. Polynomial and Matrix Computations. Birkhäuser, 1994. Zbl0809.65012MR1289412
  21. D.A. Bini, L. Robol, Solving secular and polynomial equations: A multiprecision algorithm. J. Comput. Appl. Math., 272, 276–292 (2014). Zbl1310.65052MR3227386
  22. D.A. Bini, L. Robol, On a class of matrix pencils and -ifications equivalent to a given matrix polynomial. Linear Algebra Appl., in Press, doi:10.1016/j.laa.2015.07.017, arXiv:1406.1025 (2014). 
  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). Zbl1290.65031MR3177956
  24. P. Boito, Y. Eidelman, L. Gemignani, Implicit QR for Rank-Structured Matrix Pencils, BIT Numerical Mathematics 54, 85–111 (2014). Zbl1266.65059MR2991921
  25. P. Boito, Y. Eidelman, L. Gemignani, I. Gohberg, Implicit QR with Compression, Indag. Math. 23, 733–761 (2012). Zbl0952.47025
  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. Zbl0916.15012MR1724795
  27. A. Böttcher, B. Silbermann, Introduction to Large Truncated Toeplitz Matrices, Springer, New York 1999. Zbl1280.47027MR3060410
  28. A. Böttcher, I. Spitkovsky, The factorization problem: Some known results and open questions, Operator Theory: Advances and App., 229, 101–122 (013). Zbl1136.65041MR2397851
  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). Zbl0646.65042MR945937
  30. R. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10, 542–550 (1989). Zbl0684.65035MR1016802
  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. Zbl0666.65030MR976165
  32. T. F. Chan. An optimal circulant preconditioner for Toeplitz systems. SIAM J. Sci. Statist. Comput., 9(4):766–771, 1988. Zbl0646.65042
  33. R. Chan, G. Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10, 104–119 (1989). Zbl0666.65030
  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 Zbl1259.15031MR2921748
  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). Zbl1198.65068MR2338469
  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). Zbl1195.65035MR2530262
  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). Zbl1139.65026MR2385737
  39. F. Di Benedetto, Gram matrices of fast algebras have a rank structure, SIAM J. Matrix Anal. Appl. 31, 526–545 (2009). Zbl1280.65027MR3137083
  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). Zbl1280.65034MR3136431
  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. Zbl1031.15014MR1999154
  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. Zbl1260.65024MR3011390
  43. M. Fiedler, A note on companion matrices. Linear Algebra and Its Applications, 372:325–331, 2003. Zbl0017.00102
  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). Zbl1186.15007MR2596623
  45. F.R. Gantmacher, M.G. Krein, Sur les matrices complètement non négatives et oscillatoires. Compositio Mathematica 4, 445–476 (1937). Zbl0848.65010MR1312096
  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. Zbl1170.15300MR662418
  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. Zbl0288.15004MR353038
  48. I. Gohberg, P. Lancaster, and L. Rodman. Matrix polynomials. Academic Press Inc., New York, 1982. Computer Science and Applied Mathematics. Zbl0254.65027MR329227
  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). Zbl0103.01003MR132755
  50. G.H. Golub, Some modified matrix eigenvalue problems, SIAM Review, 15, 318–334 (1973). Zbl0886.65013MR1470294
  51. I.J. Good, The colleague matrix, a Chebyshev analogue of the companion matrix Quart. J. Math., Oxf. Ser., 12, 61–68 (1961). Zbl0611.47018MR890515
  52. T.NT Goodman, C. A. Micchelli, G. Rodriguez, S. Seatzu, Spectral factorization of Laurent polynomials, Advances in Computational Mathematics, 7 429–454 (1997). Zbl1167.15001MR2396439
  53. U. Grenander, G. Szegő. Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. Zbl0839.65028MR1355506
  54. N. J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Zbl0931.65018MR1715813
  55. T. Kailath, A H. Sayed, Displacement Structure: theory and applications, SIAM Review, 297–386, 1995. Zbl0433.15001MR533501
  56. T. Kailath and A. H. Sayed, eds., Fast Reliable Algorithms for Matrices with Structure, SIAM Press, 1999. Zbl1103.65310MR2073063
  57. T. Kailath, S. Y. Kung and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Appl. 68, 395-407 (1979). Zbl0695.60088MR1010040
  58. F.-R. Lin, W.-K. Ching, M.K. Ng, Fast inversion of triangular Toeplitz matrices, Theoretical Computer Science, 315, 511–523 (2004). Zbl0469.60002MR1313503
  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. MR4222
  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. Zbl0028.19901MR12681
  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) Zbl0099.32403MR120492
  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) Zbl0028.19901
  63. S.V. Parter, Extreme eigenvalues of Toeplitz forms and applications to elliptic difference equations, Trans. Amer. Math. Soc., 99 (1966), pp. 153–192. Zbl1195.65057MR2679754
  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. Zbl1031.65046MR1990645
  65. F. Poloni, A note on the O ( n ) -storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices, Numer. Algorithms, 55, 115–139 (2010). Zbl1195.65057
  66. Y. Saad, Iterative methods for sparse linear systems, second Edition, SIAM, Philadelphia 2003. Zbl0877.65025MR1410714
  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. Zbl0864.65019MR1401945
  68. S. Serra Capizzano, Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matrix Anal. Appl., 17, 1007–1019 (1996). Zbl1021.15005MR1972737
  69. S. Serra Capizzano. Optimal, quasi–optimal and superlinear preconditioners for asymptotically ill–conditioned positive definite Toeplitz systems, Math. Comput. 66, 651–665 (1997). Zbl0215.27305MR279998
  70. S. Serra Capizzano, E. Tyrtyshnikov, How to prove that a preconditioner cannot be superlinear, Math. Comput. 1305-1316, (2003). Zbl0621.65025
  71. B.T. Smith, Error bounds for zeros of a polynomial based upon Gerschgorin’s theorems, J. Assoc. Comput. Math. 17, 661–674 (1970). Zbl0131.36002MR173681
  72. G. Strang, A proposal for Toeplitz matrix calculation, Stnd. Appl. Math. 74, 171–176 (1986). Zbl0841.15006MR1366576
  73. W.F. Trench, An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl. Math. 12, 515–522 (1964). Zbl0890.15006MR1484073
  74. E.E. Tyrtyshnikov, A Unifying Approach to Some Old and New Theorems on Distribution and Clustering, Linear Algebra Appl., 232 1–43 (1996). Zbl1196.65076MR2672262
  75. E.E. Tyrtyshnikov, N. Zamarashkin. Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl., 270, 15–27 (1998). Zbl1216.65045MR2678097
  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). Zbl1168.15312MR2191201
  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). Zbl1175.65045MR2378139
  78. R. Vandebril, M. Van Barel, G. Golub, N. Mastronardi, A bibliography on semiseparable matrices, Calcolo 42, 249–270 (2005) Zbl1141.65019MR2460593
  79. R. Vandebril, M. Van Barel, N. Mastronardi, Matrix Computations and Semiseparable Matrices, Vol. 1 Linear Systems. Johns Hopkins, Baltimore, Maryland, 2008. Zbl1258.65030MR3023454
  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. Zbl0522.15013MR719861
  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). Zbl1263.15010MR3023468
  82. W. Werner,A generalized companion matrix of a polynomial and some applications, Linear Algebra Appl., 55, 19–36 (1983). Zbl0194.18102MR247762
  83. P. Zhlobich, Differential qd algorithm with shifts for rank-structured matrices. SIAM J. Matrix Anal. Appl. 33, 1153–1171 (2012). Zbl1263.15010
  84. S. Zohar, Toeplitz matrix inversion: The algorithm of W.F. Trench, J. Assoc. Comput. Mach. 16, 592–601 (1967). Zbl0194.18102

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.