A Fast Cyclic Reduction Algorithm for A Quadratic Matrix Equation Arising from Overdamped Systems

Authors: Ning Dong, Bo Yu

Abstract:

We are concerned with a class of quadratic matrix equations arising from the overdamped mass-spring system. By exploring the structure of coefficient matrices, we propose a fast cyclic reduction algorithm to calculate the extreme solutions of the equation. Numerical experiments show that the proposed algorithm outperforms the original cyclic reduction and the structure-preserving doubling algorithm.

Keywords: Fast algorithm, Cyclic reduction, Overdampedquadratic matrix equation, Structure-preserving doubling algorithm

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331767

References:

[1] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen, LAPACK Users- Guide, (3rd Edition), SIAM, Philadelphia, PA, (1999).
[2] D.A. Bini, L. Gemignani and B. Meini, Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl., 343/344 (2002), pp. 21-61.
[3] D. A. Bini, B. Meini, F. Poloni, Fast solution of a certain Riccati equation through Cauchy-like matrices, ETNA., 33 (2009), pp. 84-104.
[4] C.-Y. Chiang, E.K. W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin, S.-F. Xu, Convergence analysis of the doubling algorithm for several nonliear matrix equations in the critical case, SIAM J. Matrix Anal. Appl., 31, 227-247, 2009.
[5] G.H. Golub and C.F. Van Loan, Matrix Computations, (3rd Edition), Johns Hopkins University Press, Baltimore, MD, (1996).
[6] C.-H. Guo, N. J. Higham and F. Tisseur, Detecting and solving hyperbolic quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl., 30 (2009), pp. 1593-1613.
[7] C.-H. GUO AND P. LANCASTER, Algorithms for hyperbolic quadratic eigenvalue problems, Math. Comp., 74 (2005), pp. 1777-1791.
[8] X.-X. Guo, W.-W. Lin and S.-F. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math. 103 (2006), pp. 393-412.
[9] I. Gohberg, T. Kailath and V. Olshevsky, Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Math. Comp., 64 (1995), pp. 1557-1576.
[10] G. Heinig, P. Jankowski and K. Rost, Fast inversion algorithm of Toeplitz-plus-Hankel matrices, Numer. Math., 52 (1988), pp. 665-682.
[11] N.J. Higham and H.-M. Kim, Numerical ananlysis of a quadratic matrix equation, IMA. J. Numer. Anal., 20 (2000), pp. 499-519.
[12] N.J. Higham and H.-M. Kim, Solving a quadratic matrix equation by Newton-s method with exact line search, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 303-316.
[13] T. Kailath and A.H. Sayed, Fast Reliable Algorithms for Matrices with Structure, SIAM, PA, (1999).
[14] W.-W. Lin and S.-F. Xu, Analysis of structure-preserving doubling algorithms for Riccati-type matrix equations, SIAM J. Matrix Anal. Appl. (2005).
[15] B. Meini, Efficient computation of the extreme solutions of X + A*X−1A = Q and X − A*X−1A = Q, Math. Comp., 239 (2002), pp. 1189-1204.
[16] F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., 309 (2000), pp. 339-361.
[17] F. Tisseur and K. Meerbergen, The quadratic eigenvalue problems, SIAM Rev., 43, (2001), pp. 235-286.
[18] F.-H. Wen, X.-G. Yang, Skewness of return distribution and coeffcient of risk premium. J. Syst. Sci. Complex., 22, (2009), pp. 360-371.
[19] F.-H. Wen, Z.-F. Liu, A copula-based correlation measure and its application. Int. J. Inform. Tech. Decis. Making, 8, (2009), pp: 1-15.
[20] B. Yu and N. Dong, A structure-preserving doubling algorithm for extreme solvents of quadratic matrix equations, Advanced Modeling and Optimization, 12, (2010), pp. 85-100.