Problem: find (real) roots of a system of L equations
Sum over (i,j) X_i Q_i_j_l X_j = K_l
where i,j, .. = 1,2, .. n and l= 1,2,.. L
K_l is given real vector and Q is given real n x n x L matrix.
Single polynomial of N-th degree will have N complex roots
and 0 to N real roots. Then set of two quadratic equations will
then have 0 to 4 sets of real roots, etc.
There is large amount of literature on numerical determination of zeros
of a system of polynomials, and most popular packages for symbolic algebra
maple, reduce, maxyma, ... have routines dealing with this problem.
There is no general solution - a solution which would provide
approximation with arbitrary selected precision of all roots in a
finite computer time.
Most effective algorithm, Gröbner Bases Algorithm, approximates
real solutions by rational numbers and is limited, in some cases, by
high demands on memory and CPU time.
It is a open field of study in computational algebra; At the end of
this answer I list book which provides intro to the field. For
practical purposes, one would use a symbolic algebra package
(mathematica, maple, reduce, maxyma, ...) and try to factorise the
polynomials and to reduce the system to a triangular form.
Here we focus on the theory and algorithms for general solutions:
History
http://www.math.utah.edu/~preszler/research/grobner.pdf
Overview:
Solving Algebraic Systems using Matrix Computations
Finding roots of polynomial equations,
http://www.research.att.com/areas/visualization/ papers_videos/pdf/242965-mk96.pdf
Tutorial on Gröbner Bases Algorithm
Systems of Equations
The Problem of Exact Solution of Systems of Algebraic Equations.
Questions about the Solvability of Systems of Algebraic Equations.
Solution of Linear Homogeneous Equations with Polynomial Coefficients.
http://www.symbolicnet.org/areas/GB_and_CS/groebner.html
Limitations of the method
Some theoretical problems when solving systems of polynomial equations
using Gro¨bner bases
http://portal.acm.org/citation.cfm?id=122523
Specialised packages:
http://dmoz.org/Computers/Algorithms/Computational_Algebra/
Bibliography
http://www1.elsevier.com/homepage/sac/cam/mcnamee/10.htm
http://www.risc.uni-linz.ac.at/people/wwindste/Research/GB/Bibliography/bibliography/bibliography.html
Books:
Computer algebra: systems and algorithms for algebraic computation
Pages: 267
Year of Publication: 1988
ISBN:0-12-204230-1
Authors J. H. Davenport at al.
Publisher Academic Press Ltd. London, UK, UK
http://portal.acm.org/citation.cfm?id=48243&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618
http://www.bestwebbuys.com/0122042301
SEARCH TERMS: Grobner base
roots of system of algebraic equations
roots of system of polynomial equations
zeros of multivariate polynomials
polynomials, lexicographical ordering
This answer aims to show what is known about this problem
in the technical literature. As stated on the beginning,
complete and general algorithm is not known.
I hope that this overview of the state of the art is useful.
Hedgie |