Parallel solution of certain Toeplitz least-squares problems

DOI10.1016/0024-3795(86)90161-8MaRDI QIDQ1072345zbMATH OpenOpenAlexWikidataFDO

Authors Adam W. Bojanczyk, Richard P. Brent

Publication date 1986

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(86)90161-8

zbMATH Keywords

parallel solutionregularizationsequential algorithmsystolic algorithmToeplitz least-squares problemVolterra convolution equations

Mathematics Subject Classification ID

Volterra integral equations (45D05) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical methods for integral equations (65R20)

Review text

We describe a systolic algorithm for solving a Toeplitz least-squares problem of special form. Such problems arise, for example, when Volterra convolution equations of the first kind are solved by regularization. The systolic algorithm is based on a sequential algorithm of \textit{L. Elden} [SIAM J. Sci. Statist. Comput. 5, 229-236 (1984; Zbl 0546.65013)], but we show how the storage requirements of Eldén's algorithm can be reduced from \(O(n^ 2)\) to O(n). The sequential algorithm takes time \(O(n^ 2)\); the systolic algorithm takes time O(n) using a linear systolic array of O(n) cells. We also show how large problems may be decomposed and solved on a small systolic array.

Recommendations

• scientific article; zbMATH DE number 17430
• scientific article; zbMATH DE number 17447
• scientific article; zbMATH DE number 2080145
• A systolic array for the regularization of ill-conditioned least-squares problem with triangular Toeplitz matrix
• scientific article; zbMATH DE number 3845052

Cites work

• An Efficient Algorithm for the Regularization of Ill-Conditioned Least Squares Problems with Triangular Toeplitz Matrix
• scientific article; zbMATH DE number 3845052 (Why is no real title available?)

Cited in

(13)

• A systolic array for the regularization of ill-conditioned least-squares problem with triangular Toeplitz matrix
• A parallel algorithm for discrete least squares rational approximation
• scientific article; zbMATH DE number 3845052 (Why is no real title available?)
• scientific article; zbMATH DE number 5762985 (Why is no real title available?)
• scientific article; zbMATH DE number 4056886 (Why is no real title available?)
• A Parallel Nonlinear Least-Squares Solver: Theoretical Analysis and Numerical Results
• scientific article; zbMATH DE number 2080145 (Why is no real title available?)
• An Application of Systolic Arrays to Linear Discrete Ill-Posed Problems
• scientific article; zbMATH DE number 766218 (Why is no real title available?)
• scientific article; zbMATH DE number 882132 (Why is no real title available?)
• Computational Science – ICCS 2005
• Error analysis of an APA algorithm for the parallel solution of some special Toeplitz linear systems
• Parallel Cholesky-based reduction for the weighted integer least squares problem

This page was built for publication: Parallel solution of certain Toeplitz least-squares problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072345)