Stability of QR-based fast system solvers for a subclass of quasiseparable rank one matrices

Dopico, Froilán; Olshevsky, Vadim; Zhlobich, Pavel

doi:10.1090/S0025-5718-2013-02710-X

Stability of QR-based fast system solvers for a subclass of quasiseparable rank one matrices
HTML articles powered by AMS MathViewer

by Froilán M. Dopico, Vadim Olshevsky and Pavel Zhlobich PDF

Math. Comp. 82 (2013), 2007-2034 Request permission

Abstract:

The development of fast algorithms to perform computations with quasiseparable matrices has received a lot of attention in the last decade. Many different algorithms have been presented by several research groups all over the world. Despite this intense activity, to the best of our knowledge, there is no rounding error analysis published for these fast algorithms. In this paper, we present error analyses for two fast solvers of quasiseparable linear systems when they are applied on order one quasiseparable matrices that include the diagonal in the lower triangular rank structure. Both solvers are based on computing first the QR factorization of the coefficient matrix, and their error analyses require novel structured techniques for proving rigorously that only one of the considered algorithms is backward stable, while the other one is not. Two fundamental consequences of this work are: (i) users should employ with caution fast algorithms for quasiseparable matrices since they may be unstable; and (ii) a lot of work has to be done to identify which fast algorithms for quasiseparable matrices are backward stable among the large family available in the literature.

References

T. Bella, Y. Eidelman, I. Gohberg, V. Olshevsky, and P. Zhlobich, Classifications of recurrence relations via subclasses of (H,k)-quasiseparable matrices, Numerical Linear Algebra in Signals, Systems and Control, Lecture Notes in Electrical Engineering, Springer-Verlag (2010).
S. Chandrasekaran and M. Gu, Fast and stable algorithms for banded plus semiseparable systems of linear equations, SIAM J. Matrix Anal. Appl. 25 (2003), no. 2, 373–384. MR 2047424, DOI 10.1137/S0895479899353373
S. Chandrasekaran, M. Gu, and T. Pals, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl. 28 (2006), no. 3, 603–622. MR 2262971, DOI 10.1137/S0895479803436652
Steven Delvaux and Marc Van Barel, A $QR$-based solver for rank structured matrices, SIAM J. Matrix Anal. Appl. 30 (2008), no. 2, 464–490. MR 2421453, DOI 10.1137/060654979
Patrick Dewilde and Alle-Jan van der Veen, Time-varying systems and computations, Kluwer Academic Publishers, Boston, MA, 1998. MR 1641480, DOI 10.1007/978-1-4757-2817-0
Y. Eidelman and I. Gohberg, Linear complexity inversion algorithms for a class of structured matrices, Integral Equations Operator Theory 35 (1999), no. 1, 28–52. MR 1707929, DOI 10.1007/BF01225526
Y. Eidelman and I. Gohberg, On a new class of structured matrices, Integral Equations Operator Theory 34 (1999), no. 3, 293–324. MR 1689391, DOI 10.1007/BF01300581
Y. Eidelman and I. Gohberg, A modification of the Dewilde-van der Veen method for inversion of finite structured matrices, Linear Algebra Appl. 343/344 (2002), 419–450. Special issue on structured and infinite systems of linear equations. MR 1878953, DOI 10.1016/S0024-3795(01)00363-9
Y. Eidelman and I. Gohberg, On generators of quasiseparable finite block matrices, Calcolo 42 (2005), no. 3-4, 187–214. MR 2191197, DOI 10.1007/s10092-005-0102-4
Y. Eidelman, I. Gohberg, and Vadim Olshevsky, Eigenstructure of order-one-quasiseparable matrices. Three-term and two-term recurrence relations, Linear Algebra Appl. 405 (2005), 1–40. MR 2148158, DOI 10.1016/j.laa.2005.02.039
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
Ellen Van Camp, Nicola Mastronardi, and Marc Van Barel, Two fast algorithms for solving diagonal-plus-semiseparable linear systems, Proceedings of the 10th International Congress on Computational and Applied Mathematics (ICCAM-2002), 2004, pp. 731–747. MR 2056911, DOI 10.1016/j.cam.2003.09.040
Raf Vandebril, Marc Van Barel, and Nicola Mastronardi, A note on the representation and definition of semiseparable matrices, Numer. Linear Algebra Appl. 12 (2005), no. 8, 839–858. MR 2172681, DOI 10.1002/nla.455
Raf Vandebril, Marc Van Barel, and Nicola Mastronardi, Matrix computations and semiseparable matrices. Vol. 1, Johns Hopkins University Press, Baltimore, MD, 2008. Linear systems. MR 2378139
Raf Vandebril, Marc Van Barel, and Nicola Mastronardi, Matrix computations and semiseparable matrices. Vol. II, Johns Hopkins University Press, Baltimore, MD, 2008. Eigenvalue and singular value methods. MR 2460593