Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
Gaussian Elimination
Related Publications
(21)
Inversion of generalized Cauchy matrices and other classes of structured matrices
Fast algorithms for multivariable systems
Stable and efficient algorithms for structured systems of linear equations
The stable computation of formal orthogonal polynomials
Fast algorithms for solving Cauchy linear systems
Subscribe
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
Edit
Fast Gaussian elimination with partial pivoting for matrices with displacement structure
(
Citations: 114
)
BibTex

RIS

RefWorks
Download
I. Gohberg
,
T. Kailath
,
V. Olshevsky
Fast O(n) implementation of
Gaussian elimination
with partial pivoting is designedfor matrices possessing Cauchylike displacement structure. We show how Toeplitzlike, ToeplitzplusHankellike and Vandermondelike matrices can be transformed intoCauchylike matrices by using Discrete Fourier, Cosine or Sine Transform matrices.
Journal:
Mathematics of Computation  Math. Comput.
, vol. 64, no. 212, pp. 15571576, 1995
DOI:
10.2307/2153371
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.
(
adsabs.harvard.edu
)
(
www.jstor.org
)
Citation Context
(48)
...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, Toeplitzlike, and Hankellike 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. Pan
,
et 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 Cauchylike 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 Cauchylike 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 wellknown 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 Cauchylike 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 AricoGiuseppe
,
et 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 Levinsonbased 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 GohbergKailathOlshevsky (GKO) algorithm [
8
]...
...The problem of solving a linear system with Cauchy matrixC was treated by Gohberg, Kailath and Olshevsky in [
8
]...
DARIO A. BINI
,
et al.
FAST SOLUTION OF A CERTAIN RICCATI EQUATION THROUGH CAUCHYLIKE MATRIC...
...A substantial improvement has been developed by using the displacement approach for matrices such as Cauchylike, Hankellike, Toeplitzlike, and confluent Cauchylike (see, [1, 2, 7, 11, 12,
15
, 17, 18, 20, 27, 29, 30, 36])...
Zhao Chen
.
Mapping computations
References
(8)
Displacement ranks of matrices and linear equations1
(
Citations: 152
)
T. Kailath
,
S. Kung
,
M. Morf
Journal:
Journal of Mathematical Analysis and Applications  J MATH ANAL APPL
, vol. 68, no. 2, pp. 395407, 1979
Displacement Structure: Theory and Applications
(
Citations: 246
)
Thomas Kailath
,
Ali H. Sayed
Journal:
Siam Review  SIAM REV
, vol. 37, no. 3, 1995
Displacement structure approach to ChebyshevVandermonde and related matrices
(
Citations: 25
)
T. Kailath
,
V. Olshevsky
Journal:
Integral Equations and Operator Theory  INTEGRAL EQUATION OPER THEORY
, vol. 22, no. 1, pp. 6592, 1995
Complexity of multiplication with vectors for structured matrices
(
Citations: 56
)
I. Gohberg
,
V. Olshevsky
Journal:
Linear Algebra and Its Applications  LINEAR ALGEBRA APPL
, vol. 202, pp. 163192, 1994
On Computations with Dense Structured Matrices
(
Citations: 52
)
Victor Pan
Journal:
Mathematics of Computation  Math. Comput.
, vol. 55, no. 191, pp. 179179, 1990
Sort by:
Citations
(114)
Erratum to “Construction and evaluation of a new tribometer for polymers”
Mehdi RazzaghiKashani
,
Ehsan Behazin
,
Afsaneh Fakhar
Journal:
Polymer Testing  POLYM TEST
, vol. 30, no. 8, pp. 925925, 2011
Stability of fast algorithms for structured linear systems
(
Citations: 10
)
Richard P. Brent
Journal:
Computing Research Repository  CORR
, vol. abs/1005.0, 2010
Randomized Preprocessing of Homogeneous Linear Systems of Equations
(
Citations: 5
)
Victor Y. Pan
,
Guoliang Qian
Journal:
Linear Algebra and Its Applications  LINEAR ALGEBRA APPL
, vol. 432, no. 12, pp. 32723318, 2010
A fast solver for linear systems with displacement structure
(
Citations: 1
)
Antonio AricoGiuseppe
,
Giuseppe Rodriguez
Journal:
Numerical Algorithms
, vol. 55, no. 4, pp. 529556, 2010
Block LUfactorization of confluent Vandermonde matrices
Lamine Melkemi
,
Faouzia Rajeh
Journal:
Applied Mathematics Letters
, vol. 23, no. 7, pp. 747750, 2010