Superfast algorithms for Cauchy-like matrix computations and extensions (Q1978119)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Superfast algorithms for Cauchy-like matrix computations and extensions |
scientific article |
Statements
Superfast algorithms for Cauchy-like matrix computations and extensions (English)
0 references
24 October 2001
0 references
The algorithm by \textit{M. Morf} [Doubling algorithms for Toeplitz and related equations, in: Proc. IEEE Int. Conf. on ASSP, IEEE Computer Soc. Press, Silvert Spring, MD, 954-959 (1980)] and by \textit{R. R. Bitmead} and \textit{B. D. D. Anderson} [ibid. 34, 103-116 (1980; Zbl 0458.65018)] to solve Toeplitz and Toeplitz-like systems is based on the notion of displacement rank and a divide and conquer strategy. In combination with the fast Fourier transform (FFT), this gives superfast algorithms that solve a system of size \(n\) in \(O(n\log^2 n)\) operations. In this paper, the authors develop a similar strategy for Cauchy (displacement rank 1) and Cauchy-like (displacement rank \(r\)) matrices. Here the displacement rank is with respect to the displacement operator \(\nabla A = D(q)A-AD(t)\) where \(D(q)\) and \(D(t)\) are diagonal matrices. Because matrix vector multiplications for these matrices can not be directly computed with FFT, the resulting algorithm has a complexity of \(O(nr^2\log^3n)\). In principle the algorithm works for strongly nonsingular matrices \(A\), but a technique of symmetrization and/or randomization can overcome this restriction. As by-products algorithms for determinant calculation, triangular factorization, least squares solution, and matrix inversion are obtained. The algorithms apply to matrices with entries from an arbitrary field. Comparison with other (super)fast algorithms for such matrices is also made.
0 references
Cauchy matrix
0 references
Cauchy-like matrix
0 references
superfast algorithm
0 references
displacement rank
0 references
rational interpolation
0 references
determinant
0 references
finite field
0 references
fast Fourier transform
0 references
complexity
0 references
triangular factorization
0 references
least squares solution
0 references
matrix inversion
0 references
0 references
0 references
0 references
0 references
0 references