skip to main content
10.1145/1277548.1277554acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Solving toeplitz- and vandermonde-like linear systems with large displacement rank

Published: 29 July 2007 Publication History

Abstract

Linear systems with structures such as Toeplitz-, Vandermonde-or Cauchy-likeness can be solved in O~(α2n) operations, where n is the matrix size, α is its displacement rank, and O~denotes the omission of logarithmic factors. We show that for Toeplitz-like and Vandermonde-like trices, this cost can be reduced to O~(αω--1 n), where ω is a feasible exponent for matrix multiplication over the base field. The best known estimate for ω is ω< 2.38, resulting in costs of order O~(α1.38n). We also present consequences for Hermite-Padé approximation and bivariate interpolation.

References

[1]
B. Beckermann. A reliable method for computing M-Padé approximants on arbitrary staircases. J. Comput. Appl. Math., 40(1):19--42, 1992.
[2]
B. Beckermann and G. Labahn. A uniform approach for the fast computation of matrix-type Padé approximants. SIAM J. Matrix Anal. Appl., 15(3):804--823, 1994.
[3]
B. Beckermann and G. Labahn. Fraction-free computation of matrix rational interpolants and matrix GCDs. SIAM J. Matrix Anal. Appl., 22(1):114--144, 2000.
[4]
M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In 20th Annual ACM Symp. Theory Comp., pages 301--309, 1988.
[5]
D. Bini and V. Y. Pan. Polynomial and Matrix Computations, volume 1: Fundamental Algorithms.Birkhäuser, 1994.
[6]
R. R. Bitmead and B. D. O. Anderson. Asymptotically fast solution of Toeplitz and related systems of linear equations. Linear Algebra Appl., 34:103--116, 1980.
[7]
A. Bostan, C.-P. Jeannerod, and É. Schost. Solving structured linear systems with large displacement rank. Technical report.
[8]
J. Canny, E. Kaltofen, and Y. Lakshman. Solving systems of non-linear polynomial equations faster. In ISSAC'89, pages 121--128. ACM, 1989.
[9]
D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693--701, 1991.
[10]
D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251--280, 1990.
[11]
R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193--195, 1978.
[12]
J.-G. Dumas, T. Gautier, and C. Pernet. Finite field linear algebra subroutines. In ISSAC'02, pages 63--74. ACM, 2002.
[13]
W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, and G. Villard. Solving sparse rational linear systems. In ISSAC'06, pages 63--70. ACM, 2006.
[14]
S. Gao, V. M. Rodrigues, and J. Stroomer. Gröbner basis structure of finite sets of points, preprint, 2003.
[15]
M. Gasca and T. Sauer. Polynomial interpolation in several variables. Adv. Comput. Math., 12(4):377--410, 2000.
[16]
J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, second edition, 2003.
[17]
J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials. C. Complex., 2(3):187--224, 1992.
[18]
P. Giorgi, C.-P. Jeannerod, and G. Villard. On the complexity of polynomial matrix computations. In ISSAC'03,pages 135--142. ACM, 2003.
[19]
I. Gohberg and V. Olshevsky. Complexity of multiplication with vectors for structured matrices. Linear Algebra Appl., 202:163--192, 1994.
[20]
O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algorithms, 3(1):45--56, 1982.
[21]
T. Kailath, S. Y. Kung, and M. Morf. Displacement ranks of matrices and linear equations. J. Math. Anal. Appl., 68(2):395--407, 1979.
[22]
E. Kaltofen. Asymptotically fast solution of Toeplitz-like singular linear systems. In ISSAC'94, pages 297--304. ACM, 1994.
[23]
E. Kaltofen. Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems. Mathematics of Computation, 64(210):777--806, 1995.
[24]
E. Kaltofen and Y. Lakshman. Improved sparse multivariate polynomial interpolation algorithms. In ISSAC'88,volume358 of LNCS. Springer Verlag, 467--474.
[25]
E. Kaltofen and D. Saunders. On Wiedemann's method of solving sparse linear systems. In AAECC-9, volume 539 of LNCS, pages 29--38. Springer Verlag, 1991.
[26]
I. Kaporin. The aggregation and cancellation techniques as a practical tool for faster matrix multiplication. Theor. Comput. Sci., 315(2-3):469--510, 2004.
[27]
G. Labahn, D. K. Choi, and S. Cabay. The inverses of block Hankel and block Toeplitz matrices. SIAM J. Comput., 19(1):98--123, 1990.
[28]
J. Laderman, V.Y. Pan, and X.-H. Sha. On practical algorithms for accelerated matrix multiplication. Linear Algebra Appl., 162--164:557--588, 1992.
[29]
D. Lazard. Ideal bases and primary decomposition: the case of two variables. J. Symb. Comput., 1:261--270, 1985.
[30]
M. Morf. Fast algorithms for multivariable systems.PhD thesis, Stanford University, 1974.
[31]
M. Morf. Doubling algorithms for Toeplitz and related equations. In IEEE Conference on Acoustics, Speech, and Signal Processing, pages 954--959, 1980.
[32]
T. Mulders. On short multiplications and divisions. AAECC, 11(1):69--88, 2000.
[33]
M. Nüsken and M. Ziegler. Fast multipoint evaluation of bivariate polynomials. In ESA 2004, number 3222 in LNCS, pages 544--555. Springer, 2004.
[34]
V. Y. Pan. On computations with dense structured matrices. Math. Comp., 55(191):179--190, 1990.
[35]
V. Y. Pan. Parametrization of Newton's iteration for computations with structured matrices and applications. Computers Math. Applic., 24(3):61--75, 1992.
[36]
V. Y. Pan. Structured Matrices and Polynomials. Birkhäuser Boston Inc., 2001.
[37]
V. Y. Pan and A. Zheng. Superfast algorithms for Cauchy-like matrix computations and extensions. Linear Algebra Appl., 310:83--108, 2000.
[38]
A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281--292, 1971.
[39]
J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701--717, October 1980.
[40]
A. Storjohann. Algorithms for matrix canonical forms.PhD thesis, ETH, Zürich, 2000.
[41]
A. Storjohann. Notes on computing minimal approximant bases. Technical report, Symbolic Computation Group, University of Waterloo, 2006.
[42]
V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.
[43]
M. Van Barel and A. Bultheel. A general module theoretic framework for vector M-Padé and matrix rational interpolation. Numer. Algorithms, 3:451--461, 1992.
[44]
R. Zippel. Probabilistic algorithms for sparse polynomials. In EUROSAM' 79,volume 72ofLNCS. Springer Verlag, 1979.
[45]
R. Zippel. Interpolating polynomials from their values. J. Symb. Comp., 9(3):375--403, 1990.

Cited By

View all
  • (2016)Guessing Linear Recurrence Relations of Sequence Tuplesand P-recursive Sequences with Linear AlgebraProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930926(95-102)Online publication date: 20-Jul-2016
  • (2015)Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional SequencesProceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2755996.2756673(61-68)Online publication date: 24-Jun-2015
  • (2015)Complexity of Computational Problems in Exact Linear AlgebraEncyclopedia of Applied and Computational Mathematics10.1007/978-3-540-70529-1_173(227-233)Online publication date: 21-Nov-2015
  • Show More Cited By

Index Terms

  1. Solving toeplitz- and vandermonde-like linear systems with large displacement rank

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
    July 2007
    406 pages
    ISBN:9781595937438
    DOI:10.1145/1277548
    • General Chair:
    • Dongming Wang
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 29 July 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dense linear algebra
    2. structured linear algebra

    Qualifiers

    • Article

    Conference

    ISSAC07
    Sponsor:
    ISSAC07: International Symposium on Symbolic and Algebraic Computation
    July 29 - August 1, 2007
    Ontario, Waterloo, Canada

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2016)Guessing Linear Recurrence Relations of Sequence Tuplesand P-recursive Sequences with Linear AlgebraProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930926(95-102)Online publication date: 20-Jul-2016
    • (2015)Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional SequencesProceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2755996.2756673(61-68)Online publication date: 24-Jun-2015
    • (2015)Complexity of Computational Problems in Exact Linear AlgebraEncyclopedia of Applied and Computational Mathematics10.1007/978-3-540-70529-1_173(227-233)Online publication date: 21-Nov-2015
    • (2010)Computing specified generators of structured matrix inversesProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837988(281-288)Online publication date: 25-Jul-2010
    • (2008)Efficient Inversion of Rational Maps Over Finite FieldsAlgorithms in Algebraic Geometry10.1007/978-0-387-75155-9_4(55-77)Online publication date: 2008

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media