Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Authors: Froilán M. Dopico, Vadim Olshevsky and Pavel Zhlobich
Journal: Math. Comp. 82 (2013), 2007-2034
MSC (2010): Primary 65F05, 65G50, 15A06, 15A23, 15B99
DOI: https://doi.org/10.1090/S0025-5718-2013-02710-X
Published electronically: May 14, 2013
MathSciNet review: 3073190
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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).
  • 2. 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 (2005f:65039)
  • 3. 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 (2007k:65049)
  • 4. S. Delvaux and M. Van Barel, A QR-based solver for rank structured matrices, SIAM J. Matrix Anal. Appl. 30 (2008), no. 2, 464-490. MR 2421453 (2009i:65073)
  • 5. P. Dewilde and A.-J. van der Veen, Time-varying systems and computations, Kluwer Academic Publishers, Boston, MA, 1998. MR 1641480 (99g:93001)
  • 6. Y. Eidelman and I. Gohberg, Linear complexity inversion algorithms for a class of structured matrices, Integral Equations and Operator Theory 35 (1999), no. 1, 28-52. MR 1707929 (2000k:65053)
  • 7. -, On a new class of structured matrices, Integral Equations and Operator Theory 34 (1999), no. 3, 293-324. MR 1689391 (2000e:15020)
  • 8. -, 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 (2003j:65021)
  • 9. -, On generators of quasiseparable finite block matrices, Calcolo 42 (2005), no. 3-4, 187-214. MR 2191197 (2006j:15036)
  • 10. Y. Eidelman, I. Gohberg, and V. Olshevsky, Eigenstructure of order-one-quasiseparable matrices. Three-term and two-term recurrence relations, Linear Algebra Appl. 405 (2005), 1-40. MR 2148158 (2007h:15014)
  • 11. N. J. Higham, Accuracy and stability of numerical algorithms, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606 (2003g:65064)
  • 12. E. Van Camp, N. Mastronardi, and M. Van Barel, Two fast algorithms for solving diagonal-plus-semiseparable linear systems, J. Comput. Appl. Math. 164/165 (2004), 731-747. MR 2056911 (2005a:65029)
  • 13. R. Vandebril, M. Van Barel, and N. Mastronardi, A note on the representation and definition of semiseparable matrices, Numer. Linear Algebra Appl. 12 (2005), no. 8, 839-858. MR 2172681 (2006j:15072)
  • 14. -, Matrix computations and semiseparable matrices. Vol. I: Linear systems, Johns Hopkins University Press, Baltimore, MD, 2008. MR 2378139 (2009d:15002)
  • 15. -, Matrix computations and semiseparable matrices. Vol. II: Eigenvalue and singular value methods, Johns Hopkins University Press, Baltimore, MD, 2008. MR 2460593 (2009j:15001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F05, 65G50, 15A06, 15A23, 15B99

Retrieve articles in all journals with MSC (2010): 65F05, 65G50, 15A06, 15A23, 15B99


Additional Information

Froilán M. Dopico
Affiliation: Instituto de Ciencias Matemáticas CSIC-UAM-UC3M-UCM and Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911, Leganés, Madrid, Spain
Email: dopico@math.uc3m.es

Vadim Olshevsky
Affiliation: Department of Mathematics, 196 Auditorium Road, University of Connecticut, Storrs, Connecticut 06269
Email: olshevsky@uconn.edu

Pavel Zhlobich
Affiliation: School of Mathematics, The University of Edinburgh, Mayfield Road, Edinburgh EH9 3JZ, United Kingdom
Email: P.Zhlobich@ed.ac.uk

DOI: https://doi.org/10.1090/S0025-5718-2013-02710-X
Keywords: Quasiseparable, semiseparable, QR-decomposition, backward error analysis
Received by editor(s): May 30, 2011
Received by editor(s) in revised form: January 25, 2012
Published electronically: May 14, 2013
Additional Notes: The work of F. M. Dopico was partially supported by the Ministerio de Economía y Competitividad of Spain through the research grant MTM-2009-09281.
This research was partially done while V. Olshevsky held a position as “Catedrático de Excelencia” at Universidad Carlos III de Madrid in the academic year 2009-10.
This research was partially done while P. Zhlobich visited the Department of Mathematics of Universidad Carlos III de Madrid in January–March 2010, partially funded by the Ministerio de Economía y Competitividad of Spain through the grant MTM-2009-09281
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society