Multiplicación de matrices circulantes con una matriz diagonal.

8

Sea , B i una secuencia de matrices circulantes de tamaño n × n .AiBin×n

Sabemos que se puede calcular en el tiempo cuadrática (uso FFT diagonalizar y añadir las matrices diagonales y aplicar IFFT).i=1nAiBi

Suponiendo es una matriz diagonal arbitraria (por simplicidad, deje que r sea n º raíz de la unidad y tenga en cuenta los elementos de la diagonal como todas las potencias distintas de menos de n de r ).Drnnr

¿Cuál es la complejidad de ? Sospecho que es cuadrático ya que estoy incluyendo la misma matriz diagonal ( términos O ( n ) ) en cada término.i=1nAiDBiO(n)

Considere una matriz circulante de tamaño n × n con la primera fila hecha de distintas potencias menores que n de r . Sea X i e Y i para i = 1 n ser matrices diagonales de rango completo.Rn×nnrXiYii=1n

¿Cuál es la complejidad de ? Nuevamente sospecho que esto es cuadrático.i=1nXiRYi

Las matrices y R que se definen con respecto a r son artificiales. Busco el caso de la diagonal en general D y general de rango completo circulante R .DRrD R

T ....
fuente

Respuestas:

3

i=1nXiRYiXiYiAXiiBYiiABRi=1nXiRYiRABi=1nXiRYi

i=1nAiDBiAiBiAiBiDi=1nXiRYi2n+1nn2logn
DDrirnDD

Thomas Klimpel
fuente