5
$\begingroup$

Are there any algorithms for solving nonlinear matrix equations over $\mathbb{C}$?

I am especially interested in solving polynomial nonlinear matrix equations.

For instance, let $X$ be some matrix satisfying

$$X=A+BXC+DXEXF$$

where $A,B,C,D,E,F$ are given matrices.

Of course, the equation could be in higher degree, such as

$$X=X^n+X^{n-1}+A$$

Is there an algorithm that can solve this kind of matrix equations?

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ Is there any additional information you can provide on this problem (in terms of $A,B,C,D.E,F$) - is there any reason to expect unique solutions for this system? Trivially, one would interpret this question as a system of $N^2$ equations for the entries of the $N\times N$ matrix $X$. One could then use a host of algorithms including the family of Newton methods. Which algorithm to use will depend on the structure of the equations. $\endgroup$
    – Nilima Nigam
    Commented Nov 18, 2011 at 0:25
  • 3
    $\begingroup$ Are you on $\mathbb{R}/\mathbb{C}$ or on a finite field? Do you really need the generic case, or can you get away with a simpler structure? As noted by Suvrit, the cases $AX+XD=B+XCX$ and $AX^2+BX+C=0$ are well-studied; if some of your matrices are invertible you can reduce some more cases to this form. The more general problem "here's a bunch of quadratic equations, give me a solution" is known to be NP-hard on a finite field, so you may have little luck in the generic case. $\endgroup$
    – Federico Poloni
    Commented Nov 18, 2011 at 12:42
  • $\begingroup$ @Nilima Nigam, any solution is fine. $\endgroup$
    – gondolf
    Commented Nov 21, 2011 at 12:20
  • $\begingroup$ @Federico Poloni, thank you, I prefer to consider complex field case. $\endgroup$
    – gondolf
    Commented Nov 21, 2011 at 12:21

2 Answers 2

Reset to default
4
$\begingroup$

You could solve your equations by suitably extending the methods for solving Nonsymmetric Riccati equations, see e.g.,

  1. Nonsymmetric algebraic Riccati equations and Wiener-Hopf Factorization for M-Matrices by C.-H. Guo
Improve this answer
$\endgroup$
4
  • $\begingroup$ @Thank you. What if the degree is greater than 2? $\endgroup$
    – gondolf
    Commented Nov 21, 2011 at 12:28
  • $\begingroup$ @gondolf: One can always derive a Newton-type method (don't know how easy it is to ensure convergence though). The recipe is essentially as for the scalar case. Suppose we are solving $R(X)=0$. First, compute the Fréchet derivative by checking what $R(X+E)$ looks like (expand out $R(X+E)$, keep only the terms linear in $E$, throw away the rest). Then, you'll have a map involving $R'(X)$, which could possibly be used to have a Newton-type iteration. Maybe there exists a more precise reference somewhere though! $\endgroup$
    – Suvrit
    Commented Nov 21, 2011 at 13:18
  • 1
    $\begingroup$ That article contains two methods: a specialization of Newton's method (Sec 2) and an algorithm based on the Schur decomposition (Sec 5). The first can be applied to any polynomial matrix equations with minor differences; the main one being that inverting the Jacobian won't in general be a Sylvester equation but a more complicated linear map, and there may not be a $O(n^3)$ method available for it. (cont) $\endgroup$
    – Federico Poloni
    Commented Nov 8, 2013 at 8:00
  • 1
    $\begingroup$ ...The second can be applied only to matrix equations that can be converted to an invariant subspace problem by reblocking: this is only a small subset of all possible polynomial equations, but it contains most of the "interesting" cases in practice (Riccati-type equations, unilateral equations). $\endgroup$
    – Federico Poloni
    Commented Nov 8, 2013 at 8:01
2
$\begingroup$

These are systems of polynomial equations (in entries of $X$). So use Groebner bases.

Improve this answer
$\endgroup$
5
  • $\begingroup$ A question regarding complexity from a user not used to Groebner bases methods. How does the efficiency of this approach compare to that of the following naive method?: 1) Transform original equation into a system of many-variable polynomial equations (I guess this can be lengthy unless the coefficients of the equation are sparse matrices). 2) Use standard algorithm to solve polynomial equations. Thanks. $\endgroup$
    – Juan Bermejo Vega
    Commented Nov 21, 2011 at 15:09
  • 1
    $\begingroup$ @Juan: What is "the standard algorithm to solve polynomial equations". The only one I know uses Groebner bases (it is essentially a generalization of the Gauss-Jordan method of solving systems of linear equations). Perhaps you meant finding approximate solutions? The complexity depends on the system of equations, order of variables, and other things (even Gauss-Jordan is not as easy as it seems). In fact it is a kind of art to make this algorithm working faster. There are many books on that subject. $\endgroup$
    – user6976
    Commented Nov 21, 2011 at 15:56
  • $\begingroup$ Yes, I meant numerical methods. I thought that was the original question. Thanks. en.wikipedia.org/wiki/… $\endgroup$
    – Juan Bermejo Vega
    Commented Nov 21, 2011 at 16:04
  • $\begingroup$ I guess we interpreted the question differently. There is no word "numeric" in it. Also he/she specifies that the field is $\mathbb{C}$ which is usual for the exact solutions and not quite usual for numeric solutions. On the other hand the OP's comments for the other answer seem to indicate that, indeed, he/she meant "numeric solutions". $\endgroup$
    – user6976
    Commented Nov 21, 2011 at 17:51
  • $\begingroup$ Also the Groebner basis method is sometimes good for numeric solutions too especially if there is only finitely many solutions because it reduces the problem to one polynomial equation in one variable. One can also use it in combination with numeric methods: first you simplify the system of equations using the Groebner procedure (possibly not to the very end), then use a numeric method. $\endgroup$
    – user6976
    Commented Nov 21, 2011 at 17:55

You must log in to answer this question.

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