Matrix structures and applications

 Access to full text

 Full (PDF)

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. http://www.mims.manchester.ac.uk/research/numerical-analysis/nlevp.html. 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 $\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). 
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 http://www.apmaths.uwo.ca/~rcorless/frames/PAPERS/PABV/CMP.pdf. 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\left(n\right)$-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