期刊
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
卷 35, 期 1, 页码 44-72出版社
SIAM PUBLICATIONS
DOI: 10.1137/120895755
关键词
Toeplitz least squares; superfast and stable solvers; randomized sampling; rectangular HSS matrix; URV factorization; HSS error and stability analysis
资金
- NSF [DMS-1255416, DMS-1115572, CHE-0957024]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1255416] Funding Source: National Science Foundation
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1115572] Funding Source: National Science Foundation
We present some superfast (O((m + n)log(2)(m + n)) complexity) and stable structured direct solvers for m x n Toeplitz least squares problems. Based on the displacement equation, a Toeplitz matrix T is first transformed into a Cauchy-like matrix C, which can be shown to have small off-diagonal numerical ranks when the diagonal blocks are rectangular. We generalize standard hierarchically semiseparable (HSS) matrix representations to rectangular ones, and construct a rectangular HSS approximation to C in nearly linear complexity with randomized sampling and fast multiplications of C with vectors. A new URV HSS factorization and a URV HSS solution are designed for the least squares solution. We also present two structured normal equation methods. Systematic error and stability analysis for our HSS methods is given, which is also useful for studying other HSS and rank structured methods. We derive the growth factors and the backward error bounds in the HSS factorizations, and show that the stability results are generally much better than those in dense LU factorizations with partial pivoting. Such analysis has not been done before for HSS matrices. The solvers are tested on various classical Toeplitz examples ranging from well-conditioned to highly ill-conditioned ones. Comparisons with some recent fast and superfast solvers are given. Our new methods are generally much faster, and give better (or at least comparable) accuracies, especially for ill-conditioned problems.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据