Multiplicação de matrizes circulantes com uma matriz diagonal

8

Seja , B i uma sequência de matrizes circulantes de tamanho n × n .AiBin×n

Sabemos que pode ser calculado em tempo quadrático (use FFT para diagonalizar e adicionar matrizes diagonais e aplicar IFFT).i=1nAiBi

Supondo é uma matriz diagonal arbitrário (para simplicidade, deixar R ser n th raiz da unidade e considerar os elementos da diagonal como todos os poderes distintos menos do que n de r ).Drnnr

Qual é a complexidade de ? Eu suspeito que seja quadrático, pois estou incluindo a mesma matriz diagonal (termos O ( n ) ) em cada termo.i=1nAiDBiO(n)

Considere uma matriz circulante de tamanho n × n com a primeira linha feita de potências distintas menores que n de r . Seja X i e Y i para i = 1 n sejam matrizes diagonais de classificação completa.Rn×nnrXiYii=1n

Qual é a complexidade de ? Mais uma vez, suspeito que isso seja quadrático.i=1nXiRYi

As matrizes e R definidas em relação a r são artificiais. Eu estou olhando para o caso de diagonal geral D e geral-rank completo circulant R .DRrD R

T ....
fonte

Respostas:

3

i=1nXiRYiXiYiAXiiBYiiABRi=1nXiRYiRABi=1nXiRYi

i=1nAiDBiAiBiAiBiDi=1nXiRYi2n+1nn2logn
DDrirnDD

Thomas Klimpel
fonte