Sunday, January 11, 2015

A Short Note on Automatic Algorithm Optimization via Fast Matrix Exponentiation

Alexander Borzunov has written an interesting article about his Python code that uses fast matrix exponentiation to automatically optimize certain algorithms. It's definitely a recommended read.

In his article, Alexander mentions that it's difficult to directly derive a matrix exponentiation algorithm for recursively-defined sequences such as \[
F_n = \begin{cases}
0, & n = 0\\
1, & n = 1\\
1, & n = 2\\
7(2F_{n-1} + 3F_{n-2})+4F_{n-3}+5n+6, & n \geq 3
\end{cases}
\] While it's true that it's not entirely simple, there is a relatively straightforward way to do this that's worth knowing.

The only difficultly is due to the term \(5n+6\), but we can eliminate it by setting
\(F_n = G_n + an+b\), then solving for appropriate values of \(a, b\).

Substituting and grouping terms we have \[
G_n + an+b = 7(2G_{n-1} + 3G_{n-2})+4G_{n-3} + 39an-68a+39b+5n+6,
\] and equating powers of \(n\) we need to solve the equations \[
\begin{align*}
a &= 39a+5,\\
b &= -68a+39b+6.
\end{align*}
\] Setting \(a = -\frac{5}{38}, b = -\frac{142}{361}\) we end up with the homogeneous system \[
G_n = \begin{cases}
\frac{142}{361}, & n = 0\\
\frac{379}{722}, & n = 1\\
\frac{237}{361}, & n = 2\\
7(2G_{n-1} + 3G_{n-2})+4G_{n-3}, & n \geq 3
\end{cases}
\] This is now easily cast into matrix exponentiation form using the standard method.

No comments:

Post a Comment