Se eu tiver duas matrizes e , das dimensões e , respectivamente, e quiser calcular , é mais eficiente reescrever a expressão como e só então avaliar numericamente, porque é da dimensão mas é da dimensão .$A$$B$$1000\times 2$$2\times 1000$$(AB{)}^{5000}$$A(BA{)}^{4999}B$$AB$$1000\times 1000$$BA$$2\times 2$

Eu quero resolver uma versão generalizada deste problema. Existe um algoritmo razoavelmente eficiente (não força bruta) para otimizar uma expressão que contém:

- Variáveis matriciais livres de dimensões conhecidas
- Produtos de subexpressões arbitrárias
- Subexpressões arbitrárias aumentadas para energia natural

... para que seja necessário o mínimo de trabalho para avaliar numericamente, depois de substituir as variáveis da matriz livre por valores da matriz concreta?

O problema da multiplicação da cadeia da matriz é um caso especial do meu problema.

**Editar:**

Esta é uma resposta provisória. Parece intuitivamente correto para mim, mas não tenho provas de que esteja correto. Se estiver correto, ainda estou interessado na prova. (Se não estiver correto, é claro, me corrija.)

Para cada produto elevado a uma potência, digamos , considere toda permutação cíclica dos fatores:$({A}_{1}{A}_{2}\dots {A}_{k}{)}^{n}$

- $({A}_{1}{A}_{2}\dots {A}_{k}{)}^{n}$
- ${A}_{1}({A}_{2}\dots {A}_{k}{A}_{1}{)}^{n-1}{A}_{2}\dots {A}_{k}$
- ${A}_{1}{A}_{2}({A}_{3}\dots {A}_{k}{A}_{1}{A}_{2}{)}^{n-1}{A}_{3}\dots {A}_{k}$
- ...
- ${A}_{1}{A}_{2}\dots {A}_{k-1}({A}_{k}{A}_{1}{A}_{2}\dots {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.