The DOI matches its Crossref record; 54 of the 54 references it cites were found in a registry or an index.
Conjugate Gradient Methods for Toeplitz Systems
Open accessAbstract
In this expository paper, we survey some of the latest developments in using preconditioned conjugate gradient methods for solving Toeplitz systems. One of the main results is that the complexity of solving a large class of n-by-n Toeplitz systems is reduced to $O(n\log n)$ operations as compared to $O(n\log ^2 n)$ operations required by fast direct Toeplitz solvers. Different preconditioners proposed for Toeplitz systems are reviewed. Applications to Toeplitz-related systems arising from partial differential equations, queueing networks, signal and image processing, integral equations, and time series analysis are given.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
Saad, Y., & Schultz, M. H. (1986) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0907058 · Cited by 11,154
Fundamentals of digital image processing
Jain, A. K. (1988) · Cited by 7,111
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Spectral Analysis and Time Series
Preston, D. B. (1983) · Technometrics · doi:10.1080/00401706.1983.10487866 · Cited by 5,011
Introduction to Statistical Time Series
McClave, J. T. (1978) · Technometrics · doi:10.1080/00401706.1978.10489651 · Cited by 4,252
Time Series: Theory and Methods
Brockwell, P. J., & Davis, R. A. (1991) · Springer Series in Statistics · doi:10.1007/978-1-4419-0320-4 · Cited by 4,122
Wittenmark, B. (1993) · Automatica · doi:10.1016/0005-1098(93)90162-m · Cited by 3,056
Linear and Nonlinear Programming
Luenberger, D. G., & Ye, Y. (2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-74503-9 · Cited by 2,804
Alexander, S. T. (1986) · Springer eBooks · doi:10.1007/978-1-4612-4978-8 · Cited by 2,646
Introduction to Statistical Time Series.
Chatfield, C., & Fuller, W. A. (1977) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344931 · Cited by 2,290
Introduction to Approximation Theory
Rivlin, T., & Cheney, E. W. (1969) · Mathematics of Computation · doi:10.2307/2004443 · Cited by 2,035
Adaptive filter theory (2nd ed.)
Haykin, S. (1991) · Prentice-Hall, Inc eBooks · Cited by 1,892
Toeplitz Forms and Their Applications
Grenander, U., Szegö, G., & Kac, M. (1958) · Physics Today · doi:10.1063/1.3062237 · Cited by 1,840
Morgan, D. (1986) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1986.1164869 · Cited by 1,681
Banham, M. R., & Katsaggelos, A. K. (1997) · IEEE Signal Processing Magazine · doi:10.1109/79.581363 · Cited by 1,678
Computational Frameworks for the Fast Fourier Transform
Van Loan, C. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,283
Yule, G. U. (1927) · Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character · doi:10.1098/rsta.1927.0007 · Cited by 1,275
The theory of Tikhonov regularization for Fredholm equations of the first kind
Groetsch, C. W. (1984) · Medical Entomology and Zoology · Cited by 1,160
Spectral Analysis and Time Series.
Parzen, E., & Priestley, M. B. (1984) · Journal of the American Statistical Association · doi:10.2307/2288374 · Cited by 1,123
Iterative Methods for Total Variation Denoising
Vogel, C. R., & Oman, M. E. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917016 · Cited by 1,076
Toeplitz Forms and Their Applications.
Savage, L. J., Grenander, U., & Szego, G. (1958) · Journal of the American Statistical Association · doi:10.2307/2282065 · Cited by 1,045
Time Series: Theory and Methods (2nd ed.).
Chen, R., Brockwell, P. J., & Davis, R. A. (1992) · Journal of the American Statistical Association · doi:10.2307/2290485 · Cited by 995
An exact recursion for the composite nearest-neighbor degeneracy for a 2×N lattice space
McQuistan, R. B., & Hock, J. L. (1984) · Journal of Mathematical Physics · doi:10.1063/1.526133 · Cited by 924
Convolution equations and projection methods for their solution
Gohberg, I., & Fel′dman, I. (2005) · Translations of Mathematical Monographs · doi:10.1090/mmono/041 · Cited by 692
A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
Freund, R. W. (1993) · SIAM Journal on Scientific Computing · doi:10.1137/0914029 · Cited by 623
An Algorithm for the Inversion of Finite Toeplitz Matrices
Trench, W. F. (1964) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0112045 · Cited by 557
Sondhi, M. (1978) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1978.1163057 · Cited by 539
Finite Element Solution of Boundary Value Problems: Theory and Computation
Axelsson, O., & Barker, V. A. (2014) · Cited by 511
Iterative methods for image deblurring
Biemond, J., Lagendijk, R. L., & Mersereau, R. M. (1990) · Proceedings of the IEEE · doi:10.1109/5.53403 · Cited by 460
Iterative solution of linear systems
Freund, R. W., Golub, G. H., & Nachtigal, N. M. (1992) · Acta Numerica · doi:10.1017/s0962492900002245 · Cited by 434
A new autoregressive spectrum analysis algorithm
Marple, L. (1980) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1980.1163429 · Cited by 433
A Proposal for Toeplitz Matrix Calculations
Strang, G. (1986) · Studies in Applied Mathematics · doi:10.1002/sapm1986742171 · Cited by 428
Fast solution of toeplitz systems of equations and computation of Padé approximants
Brent, R. P., Gustavson, F. G., & Yun, D. Y. Y. (1980) · Journal of Algorithms · doi:10.1016/0196-6774(80)90013-9 · Cited by 385
A unifying approach to some old and new theorems on distribution and clustering
Tyrtyshnikov, E. E. (1996) · Linear Algebra and its Applications · doi:10.1016/0024-3795(94)00025-5 · Cited by 327
Björck, Å. (1990) · Handbook of Numerical Analysis · doi:10.1016/s1570-8659(05)80036-5 · Cited by 313
(1991) · Springer Series in Information Sciences · doi:10.1007/978-3-642-58216-5 · Cited by 278
Superfast Solution of Real Positive Definite Toeplitz Systems
Ammar, G. S., & Gragg, W. B. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609005 · Cited by 258
New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices
Friedlander, B., Morf, M., Kailath, T., & Ljung, L. (1979) · Linear Algebra and its Applications · doi:10.1016/0024-3795(79)90030-2 · Cited by 206
Finite Element Solution of Boundary Value Problems: Theory and Computation
Axelsson, O., & Barker, V. A. (2001) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719253 · Cited by 201
Adaptive Signal Processing: Theory and Applications
Alexander, S. T. (2011) · Medical Entomology and Zoology · Cited by 196
Doubling algorithms for Toeplitz and related equations
Morf, M. (2005) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1980.1171074 · Cited by 161
The Solution of a Toeplitz Set of Linear Equations
Zohar, S. (1974) · Journal of the ACM · doi:10.1145/321812.321822 · Cited by 133
A new algorithm for solving Toeplitz systems of equations
de Hoog, F. (1987) · Linear Algebra and its Applications · doi:10.1016/0024-3795(87)90107-8 · Cited by 111
Approximation theory and numerical linear algebra
Trefethen, L. N. (1990) · Springer eBooks · doi:10.1007/978-1-4899-3442-0_30 · Cited by 109
Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems
Serra‐Capizzano, S. (1994) · BIT Numerical Mathematics · doi:10.1007/bf01934269 · Cited by 106
Hamming, R. W. (1989) · Prentice Hall International (UK) Ltd. eBooks · Cited by 97
Matrix Methods for Queuing Problems
Kaufman, L. (1983) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0904037 · Cited by 81
QR factorization of Toeplitz matrices
Bojańczyk, A. W., Brent, R. P., & Hoog, F. R. D. (1986) · Numerische Mathematik · doi:10.1007/bf01389431 · Cited by 81
Polynomials defined by a difference system
Baxter, G. (1961) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(61)90033-6 · Cited by 80
Fast decimation-in-time algorithms for a family of discrete sine and cosine transforms
Yip, P. C. Y., & Rao, K. R. (1984) · Circuits Systems and Signal Processing · doi:10.1007/bf01599167 · Cited by 66
Fast Transform Based Preconditioners for Toeplitz Equations
Boman, E. C., & Koltracht, I. (1995) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479893254269 · Cited by 35
Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
Chun, J., & Kailath, T. (1991) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0612010 · Cited by 33
Optimal regularization parameter estimation for image restoration
Reeves, S. J., & Mersereau, R. M. (1991) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.45377 · Cited by 15
Cited by
Fast Discrete Curvelet Transforms
Candès, E., Demanet, L., Donoho, D., & Ying, L. (2006) · Multiscale Modeling & Simulation · doi:10.1137/05064182x · Cited by 2,573
Factorization strategies for third-order tensors
Kilmer, M. E., & Martin, C. D. (2011) · Linear Algebra and its Applications · doi:10.1016/j.laa.2010.09.020 · Cited by 1,349
Fast, robust total variation-based reconstruction of noisy, blurred images
Vogel, C. R., & Oman, M. E. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.679423 · Cited by 601
Statistical models of fracture
Alava, M. J., Nukala, P. K. V. V., & Zapperi, S. (2006) · Advances in Physics · doi:10.1080/00018730300741518 · Cited by 588
Analysis of Half-Quadratic Minimization Methods for Signal and Image Recovery
Nikolova, M., & Ng, M. K. (2005) · SIAM Journal on Scientific Computing · doi:10.1137/030600862 · Cited by 478
Self-citation
Metadata
- Authors
- Chan, R. H., & Ng, M. K.
- Venue
- SIAM Review
- Published
- 1996-09
- Volume
- 38
- Issue
- 3
- Pages
- 427-482
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2005041367
- Cited by
- 801
- References
- 54
- FWCI
- 28.34
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.