article

Free access

The Exact Solution of Systems of Linear Equations with Polynomial Coefficients

Author:

Michael T. McClellanAuthors Info & Claims

Journal of the ACM (JACM), Volume 20, Issue 4

Pages 563 - 588

https://doi.org/10.1145/321784.321787

Published: 01 October 1973 Publication History

PDF eReader

References

[1]

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

Google Scholar

[2]

BIRKHOFF, G., AND M^CLANE, S. A Survey of Modern Algebra, 3rd Ed., Macmillan, New York, 1965.

Google Scholar

[3]

BODWIG, E. Matrix Calculus. Interscience, New York, 1959.

Google Scholar

[4]

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

Google Scholar

[5]

FRAENKEL, A. S., AND LOEWENTHAL, D. Exact solutions of linear equations with rational co* efficients. J. Res. NBS 75B, 1, 2 (Jan.-June, 1971), 67-75.

Google Scholar

[6]

BROwN, W.S, HYDE, J.P.,ANDT^GuE, B.A. The ALPAK system for nonnumerical algebra on a digital computer--III : Systems of linear equations and a class of side relations. Bell Syst. Tech. J. 4,S, 2 (July 1964), 1547-1562.

Google Scholar

[7]

BROWN, W. S. The compleat Euclidean algorithm. Bell Telephone Labs. Rep., Murray Hill, N.J., June 1968.

Google Scholar

[8]

BROWN, W. S. On Euclid's algorithm and the computation of polynomial greatest common divisors. Proc. 2nd Symp. on Symbolic and Algebraic Manipulation, ACM, New York, 1971; also, J. ACM 18, 4 (Oct. 1971), 478-504.

Crossref

Google Scholar

[9]

COLLINS, G. E. Subresultants and reduced polynomial remainder sequences. J. A CM 14, 1 (Jan. 1967), 128--142.

Crossref

Google Scholar

[10]

COLLINS, G.E. Computing time analyses for some arithmetic and algebraic algorithms. Proc. 1968 Summer Inst. on Symbolic Mathematical Computation, R. Tobey, Ed., IBM Federal Systems Ctr., June 1969, pp. 195-232.

Google Scholar

[11]

COLLINS, G. E., HEINDEL, L. E., HOROWITZ, E., McCLELLAN, M. T., AND MUSSER, D.R. The SAC-1 modular arithmetic system. Computing Ctr. Tech. Rep. 10, U. of Wisconsin, Madison, Wisc., June 1969.

Google Scholar

[12]

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

[13]

COLHNS, G.E. The calculation of multivariate polynomial resultants. Proc. 2nd Symp. on Symbolic and Algebraic Manipulation, ACM, New York, 1971; also, J. ACM 18, 4 (Oct. 1971), 515-532.

Crossref

Google Scholar

[14]

COLLtNS, G.E. The SAC-1 polynomial greatest common divisor and resultant system. Computer Sci. Dep. Teeh. Rep. 145, U. of Wisconsin, Madison, Wisc., Feb. 1972.

Google Scholar

[15]

COLm NS, G. E., AND MCCLELLAN, M.T. The SAC-1 polynomial linear algebra system. Computer Sci. Dep. Tech. Rep. 154, U. of Wisconsin, Madison, Wisc., Apr. 1972.

Google Scholar

[16]

Fox, L. An Introduction to Numerical Linear Algebra. Clarendon Press, Oxford, 1964.

Google Scholar

[17]

GANT~ACHER, F.R. Matrix Theory, Vol. 1. Chelsea, New York, 1959.

Google Scholar

[18]

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

Google Scholar

[19]

KNUTH, D.E. The Art of Computer Programming, Vol. i (Fundamental Algorithms). Addison- Wesley, Reading, Mass., 1968.

Crossref

Google Scholar

[20]

KNUTH, D.E. The Art of Computer Programming, VoW. ~ (Beminumerical Algorithms). Addison- Wesley, Reading, Mass., 1969.

Crossref

Google Scholar

[21]

LIPSON, J.D. Symbolic methods for the computer solution of linear equations with applications to flow-graphs. Proc. 1968 Summer Inst. on Symbolic Mathematical Computation, Robert Tobey, Ed., IBM Federal Systems Ctr., June 1969, pp. 233-303.

Google Scholar

[22]

LIPSON, J.D. Chinese Remainder and interpolation' algorithms. Proc. 2nd Symposium on Symbolic and Algebraic Manipulation, A CM, New York, 1971, pp. 372-398.

Crossref

Google Scholar

[23]

LUTHER, H. A., AND GUSEMAN, L. F. JR. A finite sequentially compact process for the adjoints of matrices over arbitrary integral domains. Comm. ACM 5, 8 (Aug. 1962), 447-445.

Crossref

Google Scholar

[24]

McCLELLAN, M. T. The exact solution of systems of linear equations with polynomial coefficients. Computer Sci. Dep. Tech. Rep. 136 (Ph.D. Th.), U. of Wisconsin, Madison, Wisc., Sept. 1971.

Google Scholar

[25]

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

Google Scholar

[26]

RALSTON, A. A First Course in Numerical Analysis. McGraw-Hill, New York, 1965.

Google Scholar

[27]

ROSSER, J. B. A method of computing exact inverses of matrices with integer coefficients. J. Res. NBS/~9, 5 (Nov. 1952), 349-358.

Google Scholar

[28]

TAKAHASI, H., AND ISHIBASHI, Y. A new method for "exact calculation" by digital computer. Information Processing in Japan I (1961), 28-42.

Google Scholar

Cited By

View all

Chawdhry H(2024) -adic reconstruction of rational functions in multiloop amplitudes Physical Review D10.1103/PhysRevD.110.056028110:5Online publication date: 13-Sep-2024
https://doi.org/10.1103/PhysRevD.110.056028
Baier CHensel CHutschenreiter LJunges SKatoen JKlein J(2020)Parametric Markov chains: PCTL complexity and fraction-free Gaussian eliminationInformation and Computation10.1016/j.ic.2019.104504272(104504)Online publication date: Jun-2020
https://doi.org/10.1016/j.ic.2019.104504
Guerrini ELebreton RZappatore I(2019)Polynomial Linear System Solving with Errors by Simultaneous Polynomial Reconstruction of Interleaved Reed-Solomon Codes2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849582(1542-1546)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1109/ISIT.2019.8849582
Show More Cited By

Index Terms

The Exact Solution of Systems of Linear Equations with Polynomial 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. Numerical analysis
      1. Computations on matrices

Recommendations

Exact solution of linear equations
SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

The congruential method of obtaining the exact solution of a system of linear equations with integral coefficients is critically reviewed. A new and efficient test for checking that a sequence of residue solutions determines the correct integer solution ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 20, Issue 4

Oct. 1973

172 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321784

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1973

Published in JACM Volume 20, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
1,047
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)17

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chawdhry H(2024) -adic reconstruction of rational functions in multiloop amplitudes Physical Review D10.1103/PhysRevD.110.056028110:5Online publication date: 13-Sep-2024
https://doi.org/10.1103/PhysRevD.110.056028
Baier CHensel CHutschenreiter LJunges SKatoen JKlein J(2020)Parametric Markov chains: PCTL complexity and fraction-free Gaussian eliminationInformation and Computation10.1016/j.ic.2019.104504272(104504)Online publication date: Jun-2020
https://doi.org/10.1016/j.ic.2019.104504
Guerrini ELebreton RZappatore I(2019)Polynomial Linear System Solving with Errors by Simultaneous Polynomial Reconstruction of Interleaved Reed-Solomon Codes2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849582(1542-1546)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1109/ISIT.2019.8849582
Holme PTupikina L(2018)Epidemic extinction in networks: insights from the 12 110 smallest graphsNew Journal of Physics10.1088/1367-2630/aaf01620:11(113042)Online publication date: 28-Nov-2018
https://doi.org/10.1088/1367-2630/aaf016
Hutschenreiter LBaier CKlein J(2017)Parametric Markov Chains: PCTL Complexity and Fraction-free Gaussian EliminationElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.256.2256(16-30)Online publication date: 6-Sep-2017
https://doi.org/10.4204/EPTCS.256.2
Kaltofen EPernet CStorjohann AWaddell CYap CEl Din M(2017)Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error CorrectionProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087645(237-244)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087645
Boyer BKaltofen EZhi LWatt S(2014)Numerical linear system solving with parametric entries by error correctionProceedings of the 2014 Symposium on Symbolic-Numeric Computation10.1145/2631948.2631956(33-38)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2631948.2631956
Kant P(2014)Finding linear dependencies in integration-by-parts equations: A Monte Carlo approachComputer Physics Communications10.1016/j.cpc.2014.01.017185:5(1473-1476)Online publication date: May-2014
https://doi.org/10.1016/j.cpc.2014.01.017
Coxon N(2014)List decoding of number field codesDesigns, Codes and Cryptography10.1007/s10623-013-9803-x72:3(687-711)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1007/s10623-013-9803-x
Abramov SKhmelnov D(2013)Linear differential and difference systemsProgramming and Computing Software10.1134/S036176881302002339:2(91-109)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1134/S0361768813020023
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.

References

Cited By

Index Terms

Recommendations

Exact solution of linear equations

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

Approximate solution of linear ordinary differential equations with variable 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