Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

Modélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB(MODEL)oCours n 9 : Transformée de Fourier discrèteStef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 1 / 28Résumé du cours précédentCalcul matricielManipulations des matrices :1 Stockage des : ligne ou colonne2 Les BLASLes décompositions utiles et leurs applications :1 LU2 QR3 Réduction (diagonalisation, etc.)4 SVDS. Graillat (Univ. Paris 6) MODEL (cours n˚9) 2 / 28ObjectifsPrésenter l’algorithme de « Transformée de Fourier Rapide » (Fast FourierTransform ou FFT)Un des algorithmes les plus utilisés dans le monde avec des applications entraitement du signal d’imagecalcul formel (multiplication de polynômes, de grands entiers, etc)S. Graillat (Univ. Paris 6) MODEL (cours n˚9) 3 / 28Plan du cours1 Multiplication de polynômes et choix de représentation2 Évaluation et interpolation3 Racine n-ième de l’unité4 Version matricielle de la FFTS. Graillat (Univ. Paris 6) MODEL (cours n˚9) 4 / 28BibliographieAlgorithms, S. Dasgupta, C.H. Papadimitriou et U.V. Vazirani,McGraw Hill, 2006Introduction à l’algorithmique, Thomas Cormen, Charles Leiserson,Ronald Rivest et Clifford Stein, 2nd édition, Dunod, 2002The Art of Computer Programming, Volume 2 : SeminumericalAlgorithms, Donald E. Knuth, 3e édition, Addison-Wesley, 1997Modern Computer Algebra, Joachim von zur Gathen et JürgenGerhard, 2nd edition, ...