2
$\begingroup$

From practical Computer Vision task I have a system of 8 second degree equations of 8 real variables.

Six of them have general form (where a...f -- parameters, x1,...x4,y1...y4 -- variables): \begin{align} &a_{1}x_1y_1 + a_{2}x_1y_2 + \ldots + a_{12}x_4y_1 + \ldots + a_{16}x_4y_4 = 0\\ &b_{1}x_1y_1 + b_{2}x_1y_2 + \ldots + b_{12}x_4y_1 + \ldots + b_{16}x_4y_4 = 0\\ &...\\ &f_{1}x_1y_1 + f_{2}x_1y_2 + \ldots + f_{12}x_4y_1 + \ldots + f_{16}x_4y_4 = 0\\ \end{align}

But other two have form: \begin{align} x_1^2 + x_2^2 + x_3^2 + x_4^2 = 1\\ y_1^2 + y_2^2 + y_3^2 + y_4^2 = 1\\ \end{align}

So in total 8 equations, each of them has second degree. But they are a bit different from each other. For me it's really important to have a fast solution. I expect to solve such equations thousands times per second on modern PCs.

From quick research I did I came to Gröbner polynomials and other numerical methods which are actually used for the same task but formulated as a system of 3rd degree polynomials. Most of those methods describe the solution for all general forms. In my case I'm looking for something much faster based on special form of equations.

I would really appreciate any advices on techniques suitable for this task. I have a hope that for such low degree polynomials and special form of it there is a potentially fast solution.

ADDED:

This system can be reformulated as 6 homogeneous bilinear equations:

\begin{align} y^t A_i x = 0, \: \: \text{where} \: y \in R^4, x \in R^4, A_i \in R^{4\times4} \: \text{for i} \in 1:6 \end{align}

We can forget about other two equations and just try to find solution for 8 variables by having 6 equations. Then we can just normalize. From nature of this task we can have up to 10 different solutions.

My search led me to those works:

  1. Solution Theory for Systems of Bilinear Equations
  2. Systems of Bilinear Equations
  3. Solution Theory for Systems of Bilinear Equations, almost like 1st one with same coauthor.

But all of them deal with common case and their solution is general related to dimensionality of variables and amount of equations.

Here I have not a big task with square matrix and to be happy I just need one non-trivial solution.

$\endgroup$

1 Answer 1

0
$\begingroup$

If we have corresponding variables in all equations but with some of the coefficients as zero in the shorter equations, then we can set up an $8\times 8=1\times 8$ array and use Cramer's rule and the MAT verb supported in most languages to solve for all variables.

$\textbf{Update: Cramer's Rule}$ If you have set up your equations in standard form $(ax_n+bx^{n-1}+...+C=0)$, you will need to move the Cs to the $1\times8$ matrix.

The coefficients of each equation form a row of the $8\times8$ matrix. Each "same variable" coefficient is in the same column. Put zero in the column of any row corresponding to an equation that lacks that variable. The constants of each equation go in the $1\times8$ matrix.

Take the determinant of the $8\times8$ matrix and call it $d_0$ and if $d_0=0$ there are no solutions!!!

Replace column $1$ of the original $8\times8$ matrix with the $1\times8$ matrix and take the $d_1$ determinant. The solution to your first variable is $x_1=\frac{d_1}{d_0}$.

Replace column $2$ of the original $8\times8$ matrix with the $1\times8$ matrix and take the $d_2$ determinant. The solution to your first variable is $x_2=\frac{d_2}{d_0}$.

Continue through column 8.

$\endgroup$
1
  • $\begingroup$ May I ask you to expand your idea about setting 8x8 array? Those equations are in quite general form. I wouldn't expect them to have enough zeros to be simplified into set of linier equations. $\endgroup$
    – Ilia
    Sep 27, 2020 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .