Article

Free access

Asymptotically fast solution of Toeplitz-like singular linear systems

Author:

Erich KaltofenAuthors Info & Claims

ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computation

Pages 297 - 304

https://doi.org/10.1145/190347.190431

Published: 01 August 1994 Publication History

PDF eReader

References

[1]

Bitmead~ It. R. and Anderson~ B. D. O., "Asymtotically fast solution of Toeplitz and related systems of linear equations," Linear Algebra Applic. 34, pp. 103-116 (1980).

Crossref

Google Scholar

[2]

Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).

Crossref

Google Scholar

[3]

Canny, J. and Emiris, I., "An efficient algorithm for the sparse mixed resultant," in Proc. AAECC-IO, Springer Lect. Notes Comput. Sci. 673~ edited by G. Cohen, T. Mora~ and O. Moreno; pp. 89-104~ 1993.

Digital Library

Google Scholar

[4]

Coppersmith, D., "Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm," Math. Comput. 62/205, pp. 333-350 (1994).

Digital Library

Google Scholar

[5]

Delsarte, P., Genin~ Y. V., and Kamp, Y. G., "A generMization of the Levinson algorithm for ttermitian Toeplitz matrices with any rank profile," IEEE Trans. Acoustics, Speech, and Signal Process. ASSP-33/4, (19s5).

Google Scholar

[6]

DeMillo, 1~. A. and Lipton, 1%. J., "A probabilistic remark on algebraic program testing," Information Process. Letters 7/4, pp. 193-195 (1978).

Crossref

Google Scholar

[7]

Diaz, A., Hitz, M., Kaltofen, E., Lobo, A., and Valente, T., "Process scheduling in DSC and the large sparse linear systems challenge," in Proc. DISCO '93, Springer Lect. Notes Comput. Sci. 722, edited by A. Miola; pp. 66-80, 1993. Available from anonymous@fry, cs. rpi. edu in directory kaltof en.

Digital Library

Google Scholar

[8]

Feng, G. L., Wei, V. K., l~ao, T. 1%. N., and Tzeng, K. K., "True designed-distance decoding of a class of algebraic-geometric codes, Part II: fast algorithms and Toeplitz-block Toeplitz matrices," IEEE Trans. Inf Theory, ~o appear (1994).

Google Scholar

[9]

Gohberg, i., Kailath, T., and Koltracht, I., "Efficient solution of linear systems of equations with recursire structure," Linear Algebra Appiic. 80, pp. 81- 113 (1986).

Crossref

Google Scholar

[10]

Gohberg, I. C. and Semencul, A. A., "On the inversion of finite Toeplitz matrices and their continous analogues," Mat. Issled. 2, pp. 201-233 (1972). In Russian. Math. Rev. MR 50~5524.

Google Scholar

[11]

Hong, H., "Quantifier elimination for formulas constrained by quadratic equations via slope resultants," The Computer J. 36/5, pp. 439-449 (1993).

Crossref

Google Scholar

[12]

Kailath, T., Kung, S.-Y., and Morf, M., "Displacement ranks of matrices and linear equations," J. Math. Analysis Applications 68, pp. 395-407 (1979).

Crossref

Google Scholar

[13]

Kalkbrener, M., Sweedler, M., and Taylor, L., "Low degree solutions to linear equations with K{x} coefficients," J. Symbolic Comput. 16/1, pp. 75-81 (1993).

Digital Library

Google Scholar

[14]

Kaltofen, E., "Etficient Solution of Sparse Linear Systems," Lect. Notes, Dept. Comput. Sci., Itensselaer Polytech. Inst., Troy, New York, 1992. Available from anonymous@ftp, cs .rpi. edu in directory kaltofen.

Google Scholar

[15]

Kaltofen, E., "Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems," in Proc. AAECC-IO, Springer Lect. Notes Comput. Sci. 673, edited by G. Cohen, T. Mora, and O. Moreno; pp. 195-212, 1993. Available from anonymouscftp, cs. rpi. edu in directory kalto~en.

Digital Library

Google Scholar

[16]

Kaltofen, E.~ "Direct proof of a theorem by Kalkbrener, Sweedler, and Taylor~" SIGSAM Bulletin 27/4~ p. 2 (1993b). Available from anonymous@ftp, cs.rpi, edu in directory kal~ofen.

Digital Library

Google Scholar

[17]

Kaltofen, E., "Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems," Math. Comput., to appear (1994). Available from anonymousc~l;p, cs .rpi. edu in directory kaltof en.

Digital Library

Google Scholar

[18]

Kaltofen, E. and Saunders, B. D., "On Wiedemann~s method of solving sparse linear systems," in Proc. AAECC-9, Springer Lect. Notes Comput. Sci. 539; pp. 29-38, 1991. Available from anonymouscftp, ca. rpi. edu in directory kaltofen.

Digital Library

Google Scholar

[19]

Moenck, R. T., "Fast computation of GCDs," Proc. 5th ACM Syrup. Theory Comp., pp. 142-151 (1973).

Digital Library

Google Scholar

[20]

Morf, M., "Doubling algorithms for Toeplitz and related equations," in Proc. 1980 IEEE In ternat. Conf. Acoust. Speech SignM Process.; IEEE, pp. 954-959, 1980.

Google Scholar

[21]

Pan, V., "Parameterization of Newton's iteration for computations with structured matrices and applications," Computers Math. Applic. 24/3, pp. 61-75 (1992).

Crossref

Google Scholar

[22]

Sasaki, T. and Furukawa, A., "Secondary polynomial remainder sequence and an extension of the subresultant theory," J. Inform. Process 7/;I, pp. 176-184 (1984).

Google Scholar

[23]

Schwartz, J. T., "Fast probabilistic algorithms for verification of polynomial identities," J. A CM 27, pp. 701-717 (1980).

Digital Library

Google Scholar

[24]

Strassen, V., "The computational complexity of continued fractions," SIAM J. Comput. 12/1, pp. 1-27 (1983).

Crossref

Google Scholar

[25]

Trench, W., "An algorithm for the inversion of finite Toeplitz matrices," SIAM J. Appl. Math. 12, pp. 515- 522 (1964).

Crossref

Google Scholar

[26]

Zippel, l~., "Probabilistic algorithms for sparse polynomials," Proc. EUROSAM '79, Springer Lec. Notes Comp. Sci. 72, pp. 216-226 (1979).

Digital Library

Google Scholar

[27]

Zippel, It., Effective Polynomial Computations; Kluwer Academic Publ., Boston, Massachusetts, 1993; 384pp.

Google Scholar

Cited By

View all

Villard G(2024)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367(102367)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2024.102367
von zur Gathen JMatera G(2024)Interpolation by decomposable univariate polynomialsJournal of Complexity10.1016/j.jco.2024.101885(101885)Online publication date: Jun-2024
https://doi.org/10.1016/j.jco.2024.101885
Pernet CSignargout HVillard G(2024)High-order lifting for polynomial Sylvester matricesJournal of Complexity10.1016/j.jco.2023.10180380(101803)Online publication date: Feb-2024
https://doi.org/10.1016/j.jco.2023.101803
Show More Cited By

Index Terms

Asymptotically fast solution of Toeplitz-like singular linear systems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
      2. Computations on polynomials
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

On the HSS iteration methods for positive definite Toeplitz linear systems

We study the HSS iteration method for large sparse non-Hermitian positive definite Toeplitz linear systems, which first appears in Bai, Golub and Ng's paper published in 2003 [Z.-Z. Bai, G.H. Golub, M.K. Ng, Hermitian and skew-Hermitian splitting ...
A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations

We derive a stable and fast solver for nonsymmetric linear systems of equations with shift structured coefficient matrices (e.g., Toeplitz, quasi-Toeplitz, and product of two Toeplitz matrices). The algorithm is based on a modified fast QR factorization ...
New preconditioners for systems of linear equations with Toeplitz structure

In this paper, we consider applying the preconditioned conjugate gradient (PCG) method to solve system of linear equations $$T x = \mathbf b $$ where $$T$$ is a block Toeplitz matrix with Toeplitz blocks (BTTB). We first consider Level -2 circulant preconditioners based on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computation

August 1994

359 pages

ISBN:0897916387

DOI:10.1145/190347

Chairman:
Malcolm MacCallum
QMW, London, UK

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC94

Sponsor:

SIGSAM

ISSAC94: International Symposium on Symbolic and Algebraic Computation

July 20 - 22, 1994

Oxford, United Kingdom

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Villard G(2024)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367(102367)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2024.102367
von zur Gathen JMatera G(2024)Interpolation by decomposable univariate polynomialsJournal of Complexity10.1016/j.jco.2024.101885(101885)Online publication date: Jun-2024
https://doi.org/10.1016/j.jco.2024.101885
Pernet CSignargout HVillard G(2024)High-order lifting for polynomial Sylvester matricesJournal of Complexity10.1016/j.jco.2023.10180380(101803)Online publication date: Feb-2024
https://doi.org/10.1016/j.jco.2023.101803
Karpman PPernet CSignargout HVillard GChyzak FLabahn G(2021)Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like MatricesProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465542(249-256)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465542
De Sa CGu APuttagunta RRé CRudra ACzumaj A(2018)A two-pronged progress in structured dense matrix vector multiplicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175339(1060-1079)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175339
Villard GKauers MOvchinnikov ASchost É(2018)On Computing the Resultant of Generic Bivariate PolynomialsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209020(391-398)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209020
Imamoglu EKaltofen EYang ZKauers MOvchinnikov ASchost É(2018)Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial BasesProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3208999(223-230)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3208999
Hyun SLebreton RSchost ÉYap CEl Din M(2017)Algorithms for Structured Linear Systems Solving and Their ImplementationProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087659(205-212)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087659
Chowdhury MJeannerod CNeiger VSchost EVillard G(2015)Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial ApproximationsIEEE Transactions on Information Theory10.1109/TIT.2015.241606861:5(2370-2387)Online publication date: May-2015
https://doi.org/10.1109/TIT.2015.2416068
Mullen GPanario D(2013)CryptographyHandbook of Finite Fields10.1201/b15006-22(777-860)Online publication date: 17-Jun-2013
https://doi.org/10.1201/b15006-22
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the HSS iteration methods for positive definite Toeplitz linear systems

A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations

New preconditioners for systems of linear equations with Toeplitz structure