¿Para que las clases de matriz puede la matriz exponencial fácilmente calcularse?

Question

Hemos diagonal de las matrices de $A = \mbox{diag} (\lambda_1, \ldots, \lambda_n)$ para los que la matriz exponencial tiene la forma simple $e^A = \mbox{diag} (e^{\lambda_1}, \ldots, e^{\lambda_n})$, y puede ser calculada con $\mathcal{O}(n)$ tiempo de complejidad.

Hay algoritmos generales para calcular la matriz exponencial para la matriz general, tales como la Aproximación de Pade, pero funcionan cúbicos momento en el tamaño de una matriz cuadrada.

Estoy interesado en encontrar clases de matrices cuadradas para que la matriz exponencial puede ser calculada no es más difícil de lo $\mathcal{O}(n^2)$ complejidad. Es allí cualquier estructurado de las matrices que tiene esta propiedad?

Cualquier literatura/artículos sugerencias serán apreciados.

Answer 1

Matrices nilpotentes

Por ejemplo, si $A \neq O_n$ y $A^2 = O_n$ y $A^k = O_n$ % todo $k \geq 2$y

$$\exp(A) = I_n + A + \dfrac{1}{2!} A^2 + \dfrac{1}{3!} A^3 + \dfrac{1}{4!} A^4 + \cdots = I_n + A$$

---

Matrices idempotentes

Por ejemplo, si $A^2 = A$, entonces el $A^k = A$ % todo $k \geq 1$y

$$\begin{array}{rl} \exp(A) &= I_n + A + \dfrac{1}{2!} A^2 + \dfrac{1}{3!} A^3 + \dfrac{1}{4!} A^4 + \cdots\\ &= I_n + \left(1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots \right) A\\ &= I_n + e A\end{array}$$

Matrices de proyección son idempotent.

---

Matrices de involutory

Si $A$ es involutory, entonces el $A^2 = I_n$ y, por tanto,

$$A^k = \begin{cases} I_n & \text{if } k \text{ is even}\\ A & \text{if } k \text{ is odd}\end{cases}$$

Por lo tanto,

$$\begin{array}{rl} \exp(A) &= I_n + A + \dfrac{1}{2!} A^2 + \dfrac{1}{3!} A^3 + \dfrac{1}{4!} A^4 + \cdots\\ &= I_n + A + \dfrac{1}{2!} I_n + \dfrac{1}{3!} A + \dfrac{1}{4!} I_n + \cdots\\ &= \left(1 + \frac{1}{2!} + \frac{1}{4!} + \cdots \right) I_n + \left(1 + \frac{1}{3!} + \frac{1}{5!} + \cdots \right) A\\ &= \cosh (1) \, I_n + \sinh (1) \, A\end{array}$$

Answer 2

Circulantes matrices debe ser capaz de ser exponentiated en menos de $n^2$ del tiempo. Usted puede diagonalize ellos a través de la FFT y, a continuación, exponentiate la diagonal de la matriz.

EDITAR: Creo firmemente que no singular matrices de Toeplitz puede tener su exponenciación aproxima bien la suficiente rapidez como por la combinación de los resultados de

http://www.sciencedirect.com/science/article/pii/0024379589907179

y

http://www.cis.umac.mo/~fsthws/newpapers/resumen/ps091108.pdf