article

Free access

The Exact Solution of Linear Equations with Rational Function Coefficients

Editor: Johyn R. Rice Author:

Michael T. McClellanAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 3, Issue 1

Pages 1 - 25

https://doi.org/10.1145/355719.355720

Published: 01 March 1977 Publication History

PDF eReader

References

[1]

BAREISS, E.H. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comp. ~2, 103 (July 1968), 565-578.

Google Scholar

[2]

BOROSH, I., AND FRAENKEL, A.S. Exact solutions of linear equations with rational coefficients by congruence techniques. Math. Comp. $0, 93 (Jan. 1966), 107-112.

Google Scholar

[3]

BROWN, W.S. On Euclid's algorithm and the computation of polynomial greatest common divisors. J. ACM 18, 4 (Oct. 1971), 478--504.

Crossref

Google Scholar

[4]

COLLINS, G.E. Computing time analyses for some arithmetic and algebraic algorithms. Proc. 1968 Summer Inst. Symbolic Math. Comput., R. Tobey, Ed., IBM Federal Systems Div., Bethesda, Md., June 1969, pp. 195-232.

Google Scholar

[5]

COLLINS, G.E. The SAC-1 system: An introduction and survey. Proc. 2nd Symp. on Symbolic and Algebraic Manipulation, ACM, New York, 1971, pp. 144-152.

Crossref

Google Scholar

[6]

COLLINS, G.E. The calculation of multivariate polynomial resultants, j. ACM I8, 4 (Oct. 1971), 515-532.

Crossref

Google Scholar

[7]

COLLINS, G.E. The SAC-1 polynomial greatest common divisor and resultant system. Tech. Rep. No. 145, Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., Feb. 1972.

Google Scholar

[8]

COLLINS, G.E., AND MCCLELLAN, M.T. The SAC-1 polynomial linear algebra system. Tech. Rep. No. 154, Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., April 1972.

Google Scholar

[9]

COLLINS, G.E. Computer algebra of polynomials and rational functions. Amer. Math. Monthly 80, 7 (Aug.-Sept. 1973), 725-755.

Google Scholar

[10]

FORSYTHE, G., AND MOLER, C.B. Computer Solution of Linear Algebraic Systems. Prentice- Hall, Englewood Cliffs, N.J., 1967.

Google Scholar

[11]

Ga~.GORY, R.T., AND KARNEr, D.L. A Collection of Matrices for Testing Computational Alqorithms. Wiley, New York, 1969.

Google Scholar

[12]

GRISS, M. The algebraic solution of large sparse systems of linear equations using reduce 2. Proc. 1974 ACM Annum Conf., Nov. 1974, pp. 105-111.

Crossref

Google Scholar

[13]

HOROWITZ, E., AND S~HNI, S. On computing the exact determinant of matrices with polynomial entries. J. ACM $~, 1 (Jan. 1975), 38-50.

Crossref

Google Scholar

[14]

HOWELL, J.A., XND GREGORY, R.T. An algorithm for solving linear algebraic equations using residue arithmetic. BIT 9 (1969), 200-234, 324-337.

Google Scholar

[15]

HOWELL, J.A., AND GREGORY, R.T. Solving linear equations using residue arithmeticalgorithm II, BIT 10 (1970), 23-37.

Google Scholar

[16]

KNUTH, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 2nd ed., 1973.

Crossref

Google Scholar

[17]

KNUTH, D.E. The Art of Computer Programming, Vol. ~: Seminumerical Algorithms. Addison-Wesley, Reading, Mass., 1969.

Crossref

Google Scholar

[18]

LiPso~, J.D. Symbolic methods for the computer solution of linear equations with applications to flowgraphs. Proc. 1968 Summer Inst. Symbolic Math. Comp., R. Tobey Ed., IBM Federal Systems Div., Bethesda, Md., June 1969, pp. 233-303.

Google Scholar

[19]

MCCLELLAN, M.T. The exact solution of systems of linear equations with polynomial coefficients. Tech. Rep. No. 136 (Ph.D. Th.), Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., Sept. 1971 (available as PB204590, NTIS, Springfield, Va).

Google Scholar

[20]

MCCLELLAN, M.T. The exact solution of systems of linear equations with polynomial coefficients. J. ACM ~0, 4 (Oct. 1973), 563-588.

Crossref

Google Scholar

[21]

MCCLELLAN, M.T. A comparison of algorithms for the exact solution of linear equations with polynomial coefficients. Tech. Rep. No. TR-290, Comptr. Sci. Ctr., U. of Maryland, College Park, Md., Jan. 1974 (available as PB228460, NTIS, Springfield, Va).

Google Scholar

[22]

McCLELLAN, M.T. The exact solution of linear equations with rational function coefficients. Tech. Rep. TR-341, Comptr. Sci. Center, U. of Maryland, College Park, Md., Oct. 1974.

Google Scholar

[23]

MCCLELLAN, M.T. The exact solution of linear equations: Density vs. sparsity. (in preparation).

Google Scholar

[24]

MUSSER, D.R. Multivariate polynomial factorization. J. ACM ~~, 2 (April 1975), 291-308.

Crossref

Google Scholar

[25]

NEWMAN, M. Solving equations exactly. J. Res. Nat. Bur. Standards 71B, 4 (Oct.-Dec. 1967), 171-179.

Google Scholar

[26]

REID, J.K., Ed. Large Sparse Sets of Linear Equations. Academic Press, New York,I 1971.

Google Scholar

[27]

R~EINSOLDT, W.C., AND MESZTENYI, C.K. Programs for the solution of large sparse matrix problems based on the arc-graph structure. Tech. Rep. TR-262, Comptr. Sci. Center, U. of Maryland, College Park, Md., Sept. 1973.

Google Scholar

[28]

ROSE, D.J., AND WILLOUGHBY, R.A. Eds., Sparse Matrices and Their Applications. Plenum Press, New York, 1972.

Google Scholar

[29]

TAK~IASI, H., AND ISH~SASHI, Y. A New Method for "Exact calculation" by digital computer. Information Processing in Japan i (1961), 28-42.

Google Scholar

[30]

TODD, J. The condition of finite segments of the Hilbert matrix. In Contributions to the Solution of Systems of Linear Equations and the Determination of Eigenvalues, Taussky, O. Ed., Applied Math. Ser., Vol. 39, U.S. Nat. Bur. Standards, 1954, pp. 109-116.

Google Scholar

Cited By

View all

Abbondati MGuerrini ELebreton R(2024)Decoding Simultaneous Rational Evaluation CodesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669686(153-161)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669686
Guerrini ELebreton RZappatore IChyzak FLabahn G(2021)Polynomial Linear System Solving with Random ErrorsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465548(171-178)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465548
Schuster AHippe P(1992)Inversion of polynomial matrices by interpolationIEEE Transactions on Automatic Control10.1109/9.11963837:3(363-365)Online publication date: Mar-1992
https://doi.org/10.1109/9.119638
Show More Cited By

Index Terms

The Exact Solution of Linear Equations with Rational Function Coefficients
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. Nonlinear equations
    2. Numerical analysis

Recommendations

Approximate solution of linear ordinary differential equations with variable coefficients

In this paper, a novel, simple yet efficient method is proposed to approximately solve linear ordinary differential equations (ODEs). Emphasis is put on second-order linear ODEs with variable coefficients. First, the ODE to be solved is transformed to ...
Taylor polynomial solution of hyperbolic type partial differential equations with constant coefficients

The purpose of this study is to give a Taylor polynomial approximation for the solution of hyperbolic type partial differential equations with constant coefficients. The technique used is an improved Taylor matrix method, which has been given for ...
Solving higher order linear differential equations having elliptic function coefficients
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

We consider the problem of finding closed form solutions of a linear homogeneous ordinary differential equation having coefficients which are elliptic functions. In particular, the input coefficients are assumed to be represented as elements of C(p,p'), ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 3, Issue 1

March 1977

112 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/355719

Editor:
Johyn R. Rice

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1977

Published in TOMS Volume 3, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
635
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)11

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Abbondati MGuerrini ELebreton R(2024)Decoding Simultaneous Rational Evaluation CodesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669686(153-161)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669686
Guerrini ELebreton RZappatore IChyzak FLabahn G(2021)Polynomial Linear System Solving with Random ErrorsProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465548(171-178)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465548
Schuster AHippe P(1992)Inversion of polynomial matrices by interpolationIEEE Transactions on Automatic Control10.1109/9.11963837:3(363-365)Online publication date: Mar-1992
https://doi.org/10.1109/9.119638
Koç Ç(1992)A parallel algorithm for exact solution of linear equations via congruence techniqueComputers & Mathematics with Applications10.1016/0898-1221(92)90089-Z23:12(13-24)Online publication date: Jun-1992
https://doi.org/10.1016/0898-1221(92)90089-Z
Cabay SDomzy B(1987)Systems of linear equations with dense univariate polynomial coefficientsJournal of the ACM10.1145/28869.2887734:3(646-660)Online publication date: 1-Jul-1987
https://dl.acm.org/doi/10.1145/28869.28877
Einarsson B(1979)Bibliography on the evaluation of numerical softwareJournal of Computational and Applied Mathematics10.1016/0771-050X(79)90011-15:2(145-159)Online publication date: Jun-1979
https://doi.org/10.1016/0771-050X(79)90011-1
Cabay SLam T(1977)Congruence Techniques for the Exact Solution of Integer Systems of Linear EquationsACM Transactions on Mathematical Software10.1145/355759.3557653:4(386-397)Online publication date: 1-Dec-1977
https://dl.acm.org/doi/10.1145/355759.355765
McClellan M(1977)A Comparison of Algorithms for the Exact Solution of Linear EquationsACM Transactions on Mathematical Software10.1145/355732.3557353:2(147-158)Online publication date: 1-Jun-1977
https://dl.acm.org/doi/10.1145/355732.355735

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.

References

Cited By

Index Terms

Recommendations

Approximate solution of linear ordinary differential equations with variable coefficients

Taylor polynomial solution of hyperbolic type partial differential equations with constant coefficients

Solving higher order linear differential equations having elliptic function coefficients

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations