1
$\begingroup$

I have some large system of particular non-linear polynomial equations:

  1. each equation mentions at most three variables
  2. no variable appears with a degree larger than 1.

I'm not an expert in this area but I think these are called "multilinear" polynomials, and in particular "trilinear" in my case, but I have the additional constraint that there are only three variable mentioned in each equation.

For example:

\begin{equation} \begin{aligned} 3x_1x_2x_3 + 2x_2x_3 - 3x_1x_3 + 1 &= 0\\ \ldots &= \ldots \\ 2x_1x_{42}x_{57} - 3x_1x_{57} - 2x_{42} + 2 & = 0 \end{aligned} \end{equation}

Can we "efficiently" solve these systems numerically? I know non-linear systems are hard but I've read multilinear polynomials have a lot of special properties so I suppose solving methods can benefit from ad-hoc techniques. And then, I have this additional constraint on the number of variables mentioned in each equation, which may help, if at all, at least to represent the system sparsely.

Can someone point me to relevant literature, if any, on these kind of systems with particular focus on numerical methods for solving them?

Edit: from the comments I realized the question could be more specific. Of course the obvious answer is Newton's method. However what I would like to understand is whether the particular shape of my equations can:

  1. help the method converge faster, or
  2. help the method be faster in practice/be more efficiently implementable (e.g. because of a better way to store the coefficients), or
  3. enable some different method entirely

Another detail: I expect the system to underconstrained most of the times.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think your question could be a little clearer. What aspect of solving these equations do you want to make more efficient, compared to whatever method you might already have in mind (just applying Newton's method, for example)? Also, what about the number of equations vs the number of variables? Do you expect the solution set to be 0-dimensional? $\endgroup$
    – Igor Khavkine
    Jan 9 at 11:09
  • $\begingroup$ Thanks for your comment! I have added some clarifications. Is it clearer? $\endgroup$
    – gigabytes
    Jan 9 at 12:46
  • 2
    $\begingroup$ By introducing extra variables, you can efficiently transform any system of polynomials into a system of bilinear polynomials where all the equations have the form $x_ix_j=x_k$, $x_i+x_j=x_k$, or $x_i=c$. Thus your constraints on the system do not make it any easier to solve than general polynomial systems. $\endgroup$
    – Emil Jeřábek
    Jan 9 at 13:10
  • $\begingroup$ Deleted my last comment because it made no sense. Thanks for the comment Emil! $\endgroup$
    – gigabytes
    Jan 9 at 19:41

1 Answer 1

Reset to default
2
$\begingroup$

This is kind of an indirect answer, but I would definitely encourage you to look up Smale's alpha theory. The short explanation of it is that, when you know something about the Taylor coefficients of the system, you can get explicit guarantees on the behavior of Newton's method -- for example, when an initial guess is in some quadratic convergence basin, or when two different initial guesses will converge to the same root. Here's a paper about an implementation and here are some slides from a talk.

The particular algebraic properties of your system tell you something interesting that you can use in this respect. For example, knowing that the system is trilinear, the $\gamma$ factor that appears on slide 14 of the talk / equation 2 of the linked paper is easier to calculate knowing that all the derivatives after 4 or higher are zero.

Improve this answer
$\endgroup$

You must log in to answer this question.

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