Academic
Publications
Fast Gaussian elimination with partial pivoting for matrices with displacement structure

Fast Gaussian elimination with partial pivoting for matrices with displacement structure,10.2307/2153371,Mathematics of Computation,I. Gohberg,T. Kail

Fast Gaussian elimination with partial pivoting for matrices with displacement structure   (Citations: 114)
BibTex | RIS | RefWorks Download
Fast O(n) implementation of Gaussian elimination with partial pivoting is designedfor matrices possessing Cauchy-like displacement structure. We show how Toeplitz--like, Toeplitz-plus-Hankel--like and Vandermonde-like matrices can be transformed intoCauchy--like matrices by using Discrete Fourier, Cosine or Sine Transform matrices.
Journal: Mathematics of Computation - Math. Comput. , vol. 64, no. 212, pp. 1557-1576, 1995
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...with pivoting run either in cubic time based on Gaussian elimination or SVD or in quadratic time in [26], based on the displacement transformation method, proposed in [48] (see our Remark 2.1 and [52, Sections 4.8, 4.9, and 5.6] on this method)...
    • ...The above techniques of displacement transformation for algorithm design were proposed in [48] and refined in [24], [26], and [28] to devise practical algorithms for Toeplitz, Hankel, Toeplitz-like, and Hankel-like linear systems of equations...
    • ...In the algorithms in [24], [26], and [28] Vandermonde multipliers were specialized to the matrices of Discrete Fourier transform, and then the map was slightly refined versus the original maps in [48]...

    Victor Y. Panet al. Randomized Preprocessing of Homogeneous Linear Systems of Equations

    • ...This fact allows to store a structured matrix of dimension n in O(n) memory locations and, which is most important, the displacement equation usually allows to apply a fast implementation of the Gauss triangularization method (the generalized Schur algorithm) operating directly on the displacement information associated to the matrix [6, 10, 9]; see also [15, 13] for a review...
    • ...It is remarkable that other classes of structured linear systems can be reduced to a Cauchy-like system by fast transforms (see [6, 8]), for example the systems whose matrix is Toeplitz, Hankel, or Vandermonde...
    • ...As observed in [6, 10], the advantage of applying the GSA to a Cauchy-like matrix is that such a structure is invariant under rows/columns exchanges, so it is easy to include pivoting strategy in the algorithm...
    • ...On the contrary, the approach adopted in [6] consists of explicitly computing (and storing) the LU factorization of C, hence requiring O(n2)...
    • ...Some well-known classes of structured matrices which fall within this framework are reported in Table 2.1 [6, 10, 8]. The corresponding displacement matrices are dened as follows:...
    • ...whereS1(A) = ^ A 1d‘u is the rst Schur complement of A. In Lemma 1.1 of [6] it has been proved that, if A is a Cauchy-like matrix with generators G2 Cm r, H2 Cn r, and displacement vectors t2 Cm, s2 Cn, i.e., if it satises the displacement equation...
    • ...(2r +d+2)n locs: the storage is then linear in n, while the original GKO algorithm [6] requiresO(n2) locs...

    Antonio AricoGiuseppeet al. A fast solver for linear systems with displacement structure

    • ...The GKO algorithm is generally stabler [9], even though in limit cases the growth of the coefficients appearing in the Cauchylike generators may lead to instability...
    • ...Though superfast Toeplitz solvers have a lower computational cost, when the system matrix is nonsymmetric and illconditioned O(n 2 ) algorithms such as the GKO algorithm [9] are still attractive...
    • ...Accuracy measurements For the accuracy experiments, we chose four test problems, the first two inspired from Boros, Kailath and Olshevsky [5], the third taken from Gohberg, Kailath and Olshevsky [9], and the fourth from Sweet [19] (with a slight modification)...
    • ...P3 is the Gaussian Toeplitz matrix [9], i.e., the Toeplitz matrix defined by...
    • ...,w ith sizen = 512 and different choices of the parameter a ∈ (0, 1). It is an interesting test case, since it is a matrix for which the Levinson-based Toeplitz solvers are unstable [9]...

    Federico Poloni. A note on the

    • ...This result enables us to provide an algorithm which implements CR with complexity O(n2) based on a modification of the Gohberg-Kailath-Olshevsky (GKO) algorithm [8]...
    • ...The problem of solving a linear system with Cauchy matrixC was treated by Gohberg, Kailath and Olshevsky in [8]...

    DARIO A. BINIet al. FAST SOLUTION OF A CERTAIN RICCATI EQUATION THROUGH CAUCHY-LIKE MATRIC...

    • ...A substantial improvement has been developed by using the displacement approach for matrices such as Cauchy-like, Hankel-like, Toeplitz-like, and confluent Cauchy-like (see, [1, 2, 7, 11, 12, 15, 17, 18, 20, 27, 29, 30, 36])...

    Zhao Chen. Mapping computations

Sort by: