I am looking for an algorithm to solve systems made of linear AND
quadratic equations of the form:

 A X = 0
 X^T Q_i X = k_i^2 for i = 1..n

My idea is to infer quadratic equations from the linear part (it is
easy to create many of them) to get only quadratic equations and solve
them by linearization.

Is there a better way ?

---

Request for Question Clarification by hedgie-ga on 11 Aug 2006 01:45 PDT

Vincent
    1)    Are you interested in numerical solution?
  You do not need to linearize, and it may be only one available in most cases.

   2) Your notation is a bit unclear, perhaps yoy can post a link to a gif?

 I suppose   X.i  (i,j =1,2, ... n)  is n unknown

 A is  (n x n ?? ) matrix ?  (of rank n?)

 X Q X  is quadratic form

  what is k_i   ??

 ^  means power?

Hedgie

---

Clarification of Question by vincent72-ga on 15 Aug 2006 00:14 PDT

Hi Hedgie, thanks for your interest,

1) yes I am just looking for a numerical solution.

2) I used LaTeX conventions:
^ states the following character is an exponant
_ states the following character is an index

X is a n-vector of unknowns
A is m x n matrix with m > n but   rank(A) < n
the k_i are just real numbers, some are 0, some aren't

I have more linear equations than quadratic ones. I have a very vague
intuition that (number of quadratic equations + rank A) = n but it can
be wrong.

vincent

---

Request for Question Clarification by hedgie-ga on 21 Aug 2006 07:03 PDT

Hi Vincent

    I can find a (free) numerical library, which will  contain
routines necessary to solve this type of sustem of eq.

     That is more then algorithm (since you get the soiurce of the program).

However, I still need to know more of  your specs: FORTRAN or c ?
         OS (windows? Linux, .. )

Or - does it matter?

         Is a subroutine sufficient (meaning, are you able to write a calling
front end..)?

Also, you did not explain      X^T   ::  is it transpose or power ?

if X is a vector  and Q is n x n matrix   then X Q X is a number, namely

 sum ove i,j ( X_i Q_i_j X_j)     ???


 not k_i  (n numbers).

Please , be  a bit less telegraphic and more consistent .

Hedgie

---

Clarification of Question by vincent72-ga on 22 Aug 2006 00:46 PDT

> I can find a (free) numerical library, which will  contain routines
necessary to solve this type of sustem of eq.
> That is more then algorithm (since you get the soiurce of the program).
> However, I still need to know more of  your specs: FORTRAN or c ? OS
(windows? Linux, .. )
> Or - does it matter? Is a subroutine sufficient (meaning, are you
able to write a calling front end..)?

C would be better than FORTRAN, the OS does not matter.

I'd prefer an algorithm than source code, but if your library provides
mathematical explanations for the source code, it's OK.

Please note that, as I said in my original question, I already have a
solution. However making quadratic equations from linear ones looks
quite awkward, and I'd like to know what "real mathematicians" would
do.

> Also, you did not explain      X^T   ::  is it transpose or power ?

How do you compute the power of a vector ? :-) Yes, it is transpose.

> if X is a vector  and Q is n x n matrix   then X Q X is a number, namely
> sum ove i,j ( X_i Q_i_j X_j)     ???
> not k_i  (n numbers).

  X^T Q X = k  is a single quadratic equation. I have several ones,
that's why in my question BOTH Q and k are indexed by i. If you
prefer, I can denote my quadratic equations by:

 X^T Q0 X = k0
 X^T Q1 X = k1
 X^T Q2 X = k2
 X^T Q3 X = k3
  ...
 where 
   Q0, Q1, Q2 are nxn matrices, and 
   k0, k1, k2... are real numbers, and
   X is a n-vector.

 They are the quadratic equations that must be solved in addition to a
linear system of the form:
 A X = 0

where rank A < n as said above.

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

I'm not sure what linearization is, but it seems to me that the best
way to get rid of the linear equations is as follows:

Get the row reduced echelon form of the matrix A. This is standard
procedure for solving a system of linear equations. It identifies the
independent variables (say, x(1) thru x(k) ) and the dependent
variables (say x(k+1) thru x(n) ). Substitute the dependencies into
the quadratic equations and simplify them to get new quadratic
equations in the independent unknowns. Then solve them using your
method.

It seems that this would be more efficient than making quadratic
equations from linear ones.

Hi Berkeleychocolate,

Linearization is a simple way to solve systems of quadratic equations.
You just turn the quadratic system into a linear one where the unknows
are products of two unknowns of the original system ie x2 y2 xy ...

It is a little bit rude but it is simple and it gives a solution in
closed form when you have enough quadratic equations --> that is why I
wanted to convert my linear eq into quadratic eq.

Your idea of using the row reduced echelon form is a good one, but I
am not sure I will get enough equations for the linearization.

vincent