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

ABSTRACT

Linear systems with structures such as Toeplitz-, Vandermonde-or Cauchy-likeness can be solved in O~(α²n) 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.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Algebraic algorithms