Accurate solution of structured linear systems via rank-revealing decompositions

作者：Dopico Froilan M; Molera Juan M^*

来源：IMA Journal of Numerical Analysis, 2012, 32(3): 1096-1116.

DOI：10.1093/imanum/drr023

• accurate solutions
• acyclic matrices
• Cauchy matrices
• diagonally dominant matrices
• graded matrices
• linear systems
• polynomial Vandermonde matrices
• rank-revealing decompositions
• structured matrices
• Vandermonde matrices

Linear systems of equations Ax = b, where the matrix A has some particular structure, arise frequently in applications. Very often, structured matrices have huge condition numbers kappa( A) = parallel to A(-1)parallel to parallel to A parallel to and, therefore, standard algorithms fail to compute accurate solutions of Ax = b. We say in this paper that a computed solution (x) over cap is accurate if parallel to(x) over cap - x parallel to/parallel to x parallel to = O( u), u being the unit roundoff. In this work we introduce a framework that allows many classes of structured linear systems to be solved accurately, independently of the condition number of A and efficiently, that is, with cost O(n(3)). For most of these classes no algorithms are known that are both accurate and efficient. The approach in this work relies on first computing an accurate rank-revealing decomposition of A, an idea that has been widely used in the last decades to compute singular value and eigenvalue decompositions of structured matrices with high relative accuracy. In particular, we illustrate the new method by accurately solving Cauchy and Vandermonde linear systems with any distribution of nodes, that is, without requiring A to be totally positive for most right-hand sides b.

• 出版日期2012-7