Superfast Computations with Singular Structured Matrices over Abstract Fields

V. Y. Pan (), A. Zheng, M. Abu Tabanjeh, Z. Chen and S. Providence
Additional contact information
V. Y. Pan: CUNY, Dept. Math & Comp. Sci. Lehman College
A. Zheng: Lehman College, CUNY, Dept. Math & Comp. Sci.
M. Abu Tabanjeh: Graduate School CUNY, Ph.D Programs in Math & Comp. Sci.
Z. Chen: Graduate School CUNY, Ph.D Programs in Math & Comp. Sci.
S. Providence: Graduate School CUNY, Ph.D Programs in Math & Comp. Sci.

A chapter in Computer Algebra in Scientific Computing CASC’99, 1999, pp 323-338 from Springer

Abstract: Abstract An effective superfast divide-and-conquer algorithm of Morf, 1980, and Bitmead and Anderson, 1980, computes the solution x = T −1 b to a strongly non- singular Toeplitz or Toeplitz-like linear system T x = b. The algorithm is called superfast because it runs in almost linear time, versus cubic time of Gaussian elimination and quadratic time of some known faster solutions. Recently, the algorithm was extended to similar superfast computations with n x n Cauchy and Cauchy-like matrices. We use randomization to extend this approach to superfast solution of a singular Cauchy-like linear system of equations over any field of constants and, futhermore, to superfast computation of the rank of a Cauchy-like matrix and a basis for its null space. We also ameliorate slightly Kaltofen’s superfast solver of singular Toeplitz-like linear systems in an arbitrary field. The algorithms can be easily extended to similar computations with singular Hankel-like and Vandermonde-like matrices. The applications include rational and polynomial interpolation, Pade approximation and decoding Reed-Solomon and algebraic-geometric codes.

Keywords: Null Space; Random Parameter; Input Matrix; Apply Algorithm; Principal Submatrix (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-60218-4_26

Ordering information: This item can be ordered from
http://www.springer.com/9783642602184

DOI: 10.1007/978-3-642-60218-4_26

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().