Bumped by Community user
    Bumped by Community user
    Bumped by Community user
4 added 386 characters in body
source | link

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.


Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

  • $(A_1 A_2 \ldots A_k)^n$
  • $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
  • $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
  • ...
  • $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.


Edit:

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.


Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

  • $(A_1 A_2 \ldots A_k)^n$
  • $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
  • $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
  • ...
  • $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.


Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

  • $(A_1 A_2 \ldots A_k)^n$
  • $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
  • $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
  • ...
  • $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.


Edit:

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.

3 added 807 characters in body
source | link

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.


Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

  • $(A_1 A_2 \ldots A_k)^n$
  • $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
  • $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
  • ...
  • $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.


Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

  • $(A_1 A_2 \ldots A_k)^n$
  • $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
  • $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
  • ...
  • $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

    Tweeted twitter.com/StackCompSci/status/823987722314514432
2 added 53 characters in body
source | link

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. How can IIs there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. How can I optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

  • Free matrix variables of known dimensions
  • Products of arbitrary subexpressions
  • Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

1
source | link