Optimización de una multiplicación de la matriz

Question

Dada la siguiente operación: $$\left(\begin{array}{c} f(1) \\ f(2) \\ \ldots \\ f(n)\end{array}\right) \begin{pmatrix} 1^{-1} & 1^0 & \cdots & 1^{n-2}\\ 2^{-1} & 2^0 & \cdots & 2^{n-2}\\ \vdots & \vdots & & \vdots \\ n^{-1} & n^0 & \cdots & n^{n-2}\end{pmatrix}$$

Así que un $n\times 1$ vector multiplicado por un $n\times n$ matriz. Como un ejemplo de la $n=4$ matriz sería

$$\begin{pmatrix} 1 & 1 & 1 & 1\\ 1/2 & 1 & 2 & 4 \\ 1/3 & 1 & 3 & 9 \\ 1/4 & 1 & 4 & 16\end{pmatrix}$$

Estoy buscando algo que pueda tomar ventaja de reducir la complejidad de esta operación de

$$O(n^2)$$

a algo mejor. La realización de una transformada de Fourier Discreta (DFT) para el ejemplo se utiliza la cíclico de la propiedad de la exponencial de una transformada de Fourier para abaratar la operación. Que no se aplica aquí, ya no estoy utilizando una sinusoide, pero me pregunto si hay algo que se puede lograr el mismo efecto para esta matriz.

Answer 1

Su Matriz se parece a una matriz de Vandermonde(https://en.wikipedia.org/wiki/Vandermonde_matrix). Parece que el vector-la multiplicación de la matriz puede ser acelerado para este tipo de matriz de acuerdo a este artículo http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html

Para ser más específicos, si usted tiene una matriz de Vandermonde $$\bf V = \left[\begin{array}{cccc} 1&a_1&\dots&a_1^n\\1&a_2& \dots&a_2^n\\\vdots&\vdots& \ddots&\vdots\\1&a_k& \dots&a_k^n\end{array}\right]$$ y un vector $b =\left[b_0 \dots b_n\right]$ la multiplicación es la misma como la evaluación de la polinomio $f(a) = \Sigma b_i a^i$ a los k puntos. Esto se puede hacer en $O(k\log n)$ (ver http://mathoverflow.net/questions/69476/fast-evaluation-of-polynomials). En su caso sería $O(n\log n)$ desde su matriz es cuadrada.

Voy a tratar de pensar si hay una manera de usar también el hecho de que en su caso es $a_{k+1} = a_k + 1$ a reducir aún más el cálculo

Answer 2

EDITAR Para ser más específica y sistemática podemos definir

$${\bf D}=\left[\begin{array}{cccc}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\end{array}\right], {\bf L}=\left[\begin{array}{cccc}1&0&0&0\\1&0&0&0\\1&0&0&0\\1&0&0&0\end{array}\right] , {\bf C}=\left[\begin{array}{cccc} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0 \end{array}\right]$$

• $\bf C$ es la representación de la generación de los elementos de un grupo cíclico,

• $\bf L$ actúa como una matriz de selección.

• $\bf D$ realiza cada uno de los incrementos de potencia.

Podemos entonces sistemáticamente construir la matriz de Vandermonde como este:

$${\bf V}^T={\bf D(L+D(L+D(L+DLC)C)C)C}$$

Si evaluamos esto nos da $${\bf V}^T = \left[\begin{array}{cccc} 1&1&1&1\\2&4&8&16\\3&9&27&81\\4&16&64&256\end{array}\right]$$

Por favor, tenga en cuenta que $\bf C$ $\bf L$ sólo la tecla mayús y seleccione los índices y sólo la adición y la multiplicación por $\bf D$ realiza cualquier aritmética y esas multiplicaciones son escasos. La transposición de no complicar mucho las cosas desde todas las matrices involucradas son tan simples.