Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Zyklische Matrix-Multiplikation

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Das Produkt $ C=AB$ zweier zyklischer Matrizen der Dimension $ n=2^\ell$ lässt sich mit Hilfe der schnellen Fourier-Transformation berechnen. Zunächst bestimmt man dazu mit der $ n$-fachen inversen diskreten Fourier-Transformation die Eigenwerte von $ A$ und $ B$:

$\displaystyle \lambda_j^A = \sum_{k=0}^{n-1} a_k w_n^{-jk},\quad \lambda_j^B = \sum_{k=0}^{n-1} b_k w_n^{-jk} \,, $

mit $ a$ und $ b$ den ersten Spalten von $ A$ bzw. $ B$. Dann sind

$\displaystyle \lambda_j^C = \lambda_j^A\lambda_j^B $

die Eigenwerte von $ C$, und man erhält durch $ 1/n$-fache diskrete Fourier-Transformation von $ \lambda^C$

$\displaystyle c_k = \frac{1}{n}\sum_{j=0}^{n-1}\lambda_j^C w_n^{jk} $

die Elemente der ersten Spalte von $ C$.

(Autor: Höllig)
[Verweise]
  automatisch erstellt am 29.  4. 2010