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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references