"Effiziente numerische Algorithmen 001.ps.gz" - читать интересную книгу автораVorlesungsskript Effiziente numerische Algorithmen Frank Natterer Institut f"ur Numerische und instrumentelle Mathematik WS 1994/95, Di/Fr 11-13, M 5 This page intentionally left blank. Inhaltsverzeichnis 1 Einleitung 3 1.1 Schnelle Multiplikation von Zahlen : : : : : : : : : : : : 3 1.2 Multiplikation und Inversion von Matrizen : : : : : : : : 7 2 Algebra 11 2.1 Darstellung endlicher Gruppen : : : : : : : : : : : : : : : 11 2.2 Charaktere endlicher Gruppen : : : : : : : : : : : : : : : 21 2.3 Der Chinesische Restsatz : : : : : : : : : : : : : : : : : : 31 2.4 Gruppentheorie : : : : : : : : : : : : : : : : : : : : : : : 36 3 Schnelle Fourier-Transformation 41 3.1 Fourier-Transformation und Faltung : : : : : : : : : : : : 41 3.2 Cooley-Tukey : : : : : : : : : : : : : : : : : : : : : : : : 43 3.3 Primfaktoren : : : : : : : : : : : : : : : : : : : : : : : : 50 3.4 Schnelle Faltung nach Winograd : : : : : : : : : : : : : : 56 3.5 Die schnelle Fourier-Transformation nach Winograd : : : 64 3.6 Schnelle Poisson-L"oser : : : : : : : : : : : : : : : : : : : 69 2 INHALTSVERZEICHNIS 4 Symmetrie 73 4.1 Matrizen mit Symmetrien : : : : : : : : : : : : : : : : : 73 4.2 Untergruppen : : : : : : : : : : : : : : : : : : : : : : : : 88 4.3 Direkte Produkte : : : : : : : : : : : : : : : : : : : : : : 91 4.4 Die Fourier-Transformation auf Gruppen : : : : : : : : : 95 5 Toeplitz-Matrizen 101 5.1 Der Algorithmus von Trench : : : : : : : : : : : : : : : : 101 5.2 Der Algorithmus von Morf : : : : : : : : : : : : : : : : : 106 Kapitel 1 Einleitung Wir geben einige Beispiele f"ur effiziente Algorithmen, die wir zum Teil sp"ater wieder aufgreifen und vertiefen werden. Zun"achst geht es nur darum, einen ersten Einblick in die behandelten Probleme und verwendeten Methoden zu geben. 1.1 Schnelle Multiplikation von Zahlen Seien x, y Zahlen in endlich b-adischer Darstellung, b ? 1, also x = x0 + x1b + : : : + xn\Gamma 1bn\Gamma 1 ; 0 ^ xi ! b ; y = y0 + y1b + : : : + yn\Gamma 1bn\Gamma 1 ; 0 ^ yi ! b mit ganzen Zahlen xi, yi. Gesucht ist das Produkt z = xy. Die Schulmethode soll an Hand eines Beispiels mit b = 10 und n = 3 erl"autert werden: 214 \Delta 713 |
|
|