research-article

Algorithms for Structured Linear Systems Solving and Their Implementation

Authors:

Seung Gyu Hyun,

Romain Lebreton,

Éric SchostAuthors Info & Claims

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

Pages 205 - 212

https://doi.org/10.1145/3087604.3087659

Published: 23 July 2017 Publication History

Abstract

There exists a vast literature dedicated to algorithms for structured matrices, but relatively few descriptions of actual implementations and their practical performance in symbolic computation. In this paper, we consider the problem of solving Cauchy-like systems, and its application to mosaic Toeplitz systems, in two contexts: first in the unit cost model (which is a good model for computations over finite fields), then over Q. We introduce new variants of previous algorithms and describe an implementation of these techniques and its practical behavior. We pay a special attention to particular cases such as the computation of algebraic approximants.

References

[1]

A. Arnold and E. Schost. A Truncated Fourier Transform middle product. ACM Commun. Comput. Algebra, 48(3/4):98--99, 2015.

Digital Library

[2]

J. Berthomieu and R. Lebreton. Relaxed p-adic Hensel lifting for algebraic systems. In ISSAC'12, pages 59--66. ACM, 2012.

Digital Library

[3]

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.

[4]

L. I. Bluestein. A linear filtering approach to the computation of the discrete Fourier transform. IEEE Trans. Electroacoustics, AU-18:451--455, 1970.

[5]

A. Bostan, M. F. I. Chowdhury, R. Lebreton, B. Salvy, and E. Schost. Power series solutions of singular (q)-differential equations. In ISSAC'12, pages 107--114. ACM, 2012.

Digital Library

[6]

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and E. Schost. Algorithmes efficaces en calcul formel. hal.archives-ouvertes.fr/AECF/, 2017.

[7]

A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, S. Sedoglavic, and E. Schost. Fast computation of power series solutions of systems of differential equations. In Symposium on Discrete Algorithms, SODA'07, pages 1012--1021. ACM-SIAM, 2007.

Digital Library

[8]

A. Bostan, C.-P. Jeannerod, C. Mouilleron, and E. Schost. On matrices with displacement structure: generalized operators and faster algorithms. 2016.

[9]

A. Bostan, C.-P. Jeannerod, and E. Schost. Solving structured linear systems with large displacement rank. Theor. Comput. Sci., 407(1):155--181, 2008.

Digital Library

[10]

A. Bostan, G. Lecerf, and E. Schost. Tellegen's principle into practice. In ISSAC'03, pages 37--44. ACM, 2003.

Digital Library

[11]

A. Bostan and E. Schost. Polynomial evaluation and interpolation on special sets of points. J. Complexity, 21(4):420--446, 2005.

Digital Library

[12]

A. Bostan and E Schost. Fast algorithms for differential equations in positive characteristic. In ISSAC'09, pages 47--54. ACM, 2009.

Digital Library

[13]

B. Boyer and J.-G. Dumas. Matrix multiplication over word-size modular rings using approximate formulas. ACM TOMS, 42(3):20:1--20:12, 2016.

Digital Library

[14]

D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693--701, 1991.

Digital Library

[15]

J.-P. Cardinal. On a property of Cauchy-like matrices. C. R. Acad. Sci. Paris Serie I, 388:1089--1093, 1999.

[16]

Z. Chen and V. Y. Pan. An efficient solution for Cauchy-like systems of equations. Computers Math. Applic., 48:529--537, 2004.

Digital Library

[17]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251--280, March 1990.

Digital Library

[18]

J. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., 40:137--141, 1982.

Digital Library

[19]

J.-G. Dumas, P. Giorgi, and C. Pernet. Dense linear algebra over word-size prime fields: The FFLAS and FFPACK packages. ACM TOMS, 35(3):19:1--19:42, 2008.

Digital Library

[20]

J. Durbin. The fitting of time series models. Rev. Inst. Int. Stat., 28:233--243, 1960.

[21]

FFLAS-FFPACK-Team. FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package, v2.2.2 edition, 2016. http://github.com/linbox-team/fflas-ffpack.

[22]

M. Furer. Faster Integer Multiplication. In STOC'07, pages 57--66, 2007.

Digital Library

[23]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, third edition, 2013.

Digital Library

[24]

I. Gohberg, T. Kailath, and V. Olshevsky. Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comp., 64(212):1557--1576, 1995.

Digital Library

[25]

G. Hanrot, M. Quercia, and P. Zimmermann. The Middle Product Algorithm, I. Appl. Algebra Engrg. Comm. Comp., 14(6):415--438, 2004.

Digital Library

[26]

G. Heinig and T. Amdeberhan. On the inverses of Hankel and Toeplitz mosaic matrices. In Seminar Analysis (Berlin, 1987/1988), pages 53--65. 1988.

[27]

T. Huckle. Implementation of a superfast algorithm for symmetric positive definite linear equations of displacement rank 2. volume 2296 of Proceedings of the SPIE, pages 494--503. 1994.

[28]

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.

[29]

C.-P. Jeannerod and C. Mouilleron. Computing specified generators of structured matrix inverses. In ISSAC'10, pages 281--288. ACM, 2010.

Digital Library

[30]

T. Kailath, S. Y. Kung, and M. Morf. Displacement ranks of matrices and linear equations. J. Math. Anal. Appl., 68(2):395--407, 1979.

[31]

T. Kailath and A. H. Sayed. Fast Reliable Algorithms for Matrices with Structure. SIAM, 1999.

Digital Library

[32]

E. Kaltofen. Asymptotically fast solution of Toeplitz-like singular linear systems. In ISSAC'94, pages 297--304. ACM, 1994.

Digital Library

[33]

F. Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC'14, pages 296--303. ACM, 2014.

Digital Library

[34]

R. Lebreton. Contributions to relaxed algorithms and polynomial system solving. PhD thesis, Ecole Polytechnique, Palaiseau, France, 2012.

[35]

N. Levinson. The Wiener RMS error criterion in filter design and prediction. J. Math. Phys., 25:261--278, 1947.

[36]

M. Morf. Doubling algorithms for toeplitz and related equations. In IEEE Conference on Acoustics, Speech, and Signal Processing, pages 954--959, 1980.

[37]

C. Mouilleron. Algorithmes rapides pour la resolution de problemes algebriques structures. Master's thesis, ENS Lyon, 2008.

[38]

M. Nusken and M. Ziegler. Fast multipoint evaluation of bivariate polynomials. In ESA 2004, number 3222 in LNCS, pages 544--555. Springer, 2004.

[39]

V. Olshevsky and V. Y. Pan. A unified superfast algorithm for boundary rational tangential interpolation problems and for inversion and factorization of dense structured matrices. In Proc. 39th IEEE FOCS, pages 192--201, 1998.

Digital Library

[40]

V. Y. Pan. On computations with dense structured matrices. Math. Comp., 55(191):179--190, 1990.

[41]

V. Y. Pan. Parametrization of Newton's iteration for computations with structured matrices and applications. Computers Math. Applic., 24(3):61--75, 1992.

[42]

V. Y. Pan. Structured Matrices and Polynomials. Birkhauser Boston Inc., 2001.

Digital Library

[43]

V. Y. Pan, B. Murphy, and R. E. Rosholt. Nearly optimal symbolic numerical algorithms for structured integer matrices and polynomials. In SNC'09, pages 105--114. ACM, 2009.

Digital Library

[44]

V. Y. Pan, Brian J. Murphy, and R. E. Rosholt. Unified nearly optimal algorithms for structured integer matrices. In Numerical Methods for Structured Matrices and Applications, pages 359--375. Birkhauser, 2010.

[45]

V. Y. Pan and A. Zheng. Superfast algorithms for Cauchy-like matrix computations and extensions. Linear Algebra Appl., 310:83--108, 2000.

[46]

A. Schonhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281--292, 1971.

[47]

H. Sexton, M. Shensa, and J. Speiser. Remark on a displacement-rank inversion method for Toeplitz systems. Linear Algebra Appl., 45:127--130, 1982.

[48]

V. Shoup. NTL: A library for doing number theory. http://www.shoup.net.

[49]

V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comp., 20(4):363--397, 1995.

Digital Library

[50]

W. F. Trench. An algorithm for the inversion of finite Toeplitz matrices. J. Soc. Indust. Appl. Math., 12:515--522, 1964.

Cited By

Hyun SNeiger VSchost ÉDavenport JWang DKauers MBradford R(2019)Implementations of Efficient Univariate Polynomial Matrix Algorithms and Application to Bivariate ResultantsProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326272(235-242)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326272
Pan V(2018)Fast matrix multiplication and its algebraic neighbourhoodSbornik: Mathematics10.1070/SM8833208:11(1661-1704)Online publication date: 29-Jan-2018
https://doi.org/10.1070/SM8833
Pan V(2017)Быстрое умножение матриц и смежные вопросы алгебрыFast matrix multiplication and its algebraic neighbourhoodМатематический сборникMatematicheskii Sbornik10.4213/sm8833208:11(90-138)Online publication date: 27-Oct-2017
https://doi.org/10.4213/sm8833

Index Terms

Algorithms for Structured Linear Systems Solving and Their Implementation
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Exact arithmetic algorithms
      2. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields

Recommendations

Efficient parallel factorization and solution of structured and unstructured linear systems

This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the ...
Stability Issues in the Factorization of Structured Matrices

This paper provides an error analysis of the generalized Schur algorithm of Kailath and Chun [SIAM J. Matrix Anal. Appl., 15 (1994), pp. 114--128]---a class of algorithms which can be used to factorize Toeplitz-like matrices, including block-Toeplitz ...
A basic linear algebra compiler for structured matrices
CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

Many problems in science and engineering are in practice modeled and solved through matrix computations. Often, the matrices involved have structure such as symmetric or triangular, which reduces the operations count needed to perform the computation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

July 2017

466 pages

ISBN:9781450350648

DOI:10.1145/3087604

Editor:
Michael Burr
Clemson University, USA
,
General Chair:
Chee K. Yap
New York University, USA
,
Program Chair:
Mohab Safey El Din
University Pierre et Marie Curie, France

Copyright © 2017 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Eric Schost

Conference

ISSAC '17

ISSAC '17: International Symposium on Symbolic and Algebraic Computation

July 23 - 28, 2017

Kaiserslautern, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
64
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hyun SNeiger VSchost ÉDavenport JWang DKauers MBradford R(2019)Implementations of Efficient Univariate Polynomial Matrix Algorithms and Application to Bivariate ResultantsProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326272(235-242)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326272
Pan V(2018)Fast matrix multiplication and its algebraic neighbourhoodSbornik: Mathematics10.1070/SM8833208:11(1661-1704)Online publication date: 29-Jan-2018
https://doi.org/10.1070/SM8833
Pan V(2017)Быстрое умножение матриц и смежные вопросы алгебрыFast matrix multiplication and its algebraic neighbourhoodМатематический сборникMatematicheskii Sbornik10.4213/sm8833208:11(90-138)Online publication date: 27-Oct-2017
https://doi.org/10.4213/sm8833

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents