More Web Proxy on the site http://driver.im/

Article

Free access

The exact solution of systems of linear equations with polynomial coefficients

Author:

Michael T. McClellanAuthors Info & Claims

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

Pages 399 - 414

https://doi.org/10.1145/800204.806311

Published: 23 March 1971 Publication History

Abstract

An algorithm for computing exactly a general solution to a system of linear equations with coefficients that are polynomials over the integers is presented. The algorithm applies mod-p mappings and then evaluation mappings, eventually solving linear systems of equations with coefficients in GF(p) by a special Gaussian elimination algorithm. Then by applying interpolation and the Chinese Remainder Theorem a general solution is obtained.

For a consistent system, the evaluation-interpolation part of the algorithm computes the determinantal RRE form of the mod-p reduced augmented system matrices. The Chinese Remainder Theorem then uses these to construct an RRE matrix with polynomial entries over the integers, from which a general solution is constructed. For an inconsistent system, only one mod-p mapping is needed.

The average computing time for the algorithm is obtained and compared to that for the exact division method. The new method is found to be far superior. Also, a mod-p/evaluation mapping algorithm for computing matrix products is discussed briefly.

References

[1]

Bareiss, Erwin H., "Sylvester's Identity and Multistep Integer - Preserving Gaussian Elimination," Math Comp, July, 1968.

[2]

Birkhoff, Garrett and MacLane, Saunders, A Survey of Modern Algebra, Macmillan, New York, 1965.

[3]

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

[4]

Borosh, I. and Fraenkel, A. S., "Exact Solutions of Linear Equations with Rational Coefficients by Congruence Techniques," Math Comp, Vol. 20, No. 93, Jan. 1966.

[5]

Collins, George E., "Computing Time Analysis for Some Arithmetic and Algebraic Algorithms," Proc. of the 1968 Summer Institute on Symbolic Mathematical Computation, R. Tobey (Ed.), June, 1969.

[6]

Collins, George E., Algebraic Algorithms, Prentice Hall, New Jersey (to appear).

[7]

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

[8]

Gantmacher, F. R., Matrix Theory, Vol. 1, Chelsea, New York, 1959.

[9]

Howell, J. A. and Gregory, R. T., "An Algorithm for Solving Linear Algebraic Equations Using Residue Arithmetic," BIT, 9 (1969), pp. 200-234, 324-337.

Digital Library

[10]

Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison Wesley, Reading, Mass., 1968.

Digital Library

[11]

Knuth, D. E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison Wesley, Reading, Mass., 1969.

Digital Library

[12]

Lipson, John D., "Symbolic Methods for the Computer Solution of Linear Equations with Applications to Flowgraphs," Proc. of the 1968 Summer Institute on Symbolic Mathematical Computation, R. Tobey (Ed.), June 1969.

[13]

Luther, H. A. and Guseman, L. F., Jr., "A Finite Sequentially Compact Process for the Adjoints of Matrices over Arbitrary Integral Domains," CACM, Vol. 5, No. 8, (Aug. 1962).

Digital Library

[14]

McClellan, Michael T., Algorithms for Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Ph.D. Thesis, Computer Science Dept., Univ. of Wisconsin. In preparation.

[15]

Newman, Morris, "Solving Equations Exactly," J. of Res., N.B.S., Vol. 71B, No. 4, Oct. - Dec, 1967.

[16]

Takahasi, H. and Ishibashi, Y., "A New Method for 'Exact Calculation' by a Digital Computer," Information Processing in Japan, Vol. 1 (1961), pp. 28-42.

Cited By

Yun D(1973)On algorithms for solving systems of polynomial equationsACM SIGSAM Bulletin10.1145/1086809.1086811(19-25)Online publication date: 1-Sep-1973
https://dl.acm.org/doi/10.1145/1086809.1086811
Collins G(1971)The Calculation of Multivariate Polynomial ResultantsJournal of the ACM10.1145/321662.32166618:4(515-532)Online publication date: 1-Oct-1971
https://dl.acm.org/doi/10.1145/321662.321666

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. Algebraic algorithms
      2. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Linear partial q-difference equations on q-linear lattices and their bivariate q-orthogonal polynomial solutions

Orthogonal polynomial solutions of an admissible potentially self-adjoint linear second-order partial q-difference equation of the hypergeometric type in two variables on q-linear lattices are analyzed. A q-Pearson's system for the orthogonality weight ...
Bidiagonalization of Matrices and Solution of Linear Equations

An algorithm given by Golub and Kahan [2] for reducing a general matrix to bidiagonal form is shown to be very important for large sparse matrices. The singular values of the matrix are those of the bidiagonal form, and these can be easily computed. The ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

March 1971

464 pages

ISBN:9781450377867

DOI:10.1145/800204

Copyright © 1971 ACM.

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

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGNUM: ACM Special Interest Group on Numerical Mathematics
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIAM: Society for Industrial and Applied Mathematics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 1971

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
86
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)6

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yun D(1973)On algorithms for solving systems of polynomial equationsACM SIGSAM Bulletin10.1145/1086809.1086811(19-25)Online publication date: 1-Sep-1973
https://dl.acm.org/doi/10.1145/1086809.1086811
Collins G(1971)The Calculation of Multivariate Polynomial ResultantsJournal of the ACM10.1145/321662.32166618:4(515-532)Online publication date: 1-Oct-1971
https://dl.acm.org/doi/10.1145/321662.321666

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents