Unified Divide-and-Conquer Algorithm

Victor Y. Pan
Additional contact information
Victor Y. Pan: Lehman College, CUNY, Department of Mathematics and Computer Science

Chapter Chapter 5 in Structured Matrices and Polynomials, 2001, pp 155-175 from Springer

Abstract: Abstract In this chapter, we describe a superfast divide-and-conquer algorithm for recursive triangular factorization of structured matrices. The algorithm applies over any field of constants. As a by-product, we obtain the rank of an input matrix and a basis for its null space. For a non-singular matrix, we also compute its inverse and determinant. The null space basis and the inverse are represented in compressed form, with their short displacement generators. The presentation is unified over various classes of structured matrices. Treatment of singularities is specified separately for numerical and symbolic implementations of the algorithm. The algorithm enables computations for several fundamental and celebrated problems of computer algebra and numerical rational computations.

Keywords: Null Space; Structure Matrice; Input Matrix; Operator Matrice; Rational Interpolation (search for similar items in EconPapers)
Date: 2001
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-1-4612-0129-8_5

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

DOI: 10.1007/978-1-4612-0129-8_5

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 ().