Introductie Scientific Computing (WISB 356), 2011/2012
Plaats en tijd
's dinsdags vanaf 13 september t/m 20 december, van 15.15-19.00 uur in zaal
BBL 109 op de Uithof in Utrecht. Niet op 8 november i.v.m. tentamenweek.
Vakbeschrijving
Het doel van deze cursus is een eerste orientatie
te geven op de scientific computing aan de hand van case studies uit
verschillende toepassingsgebieden. Behandeld worden veelgebruikte
technieken uit de numerieke lineaire algebra zoals het oplossen van
lineaire stelsels en eigenwaardeproblemen, zowel vol als ijl, binnen de
contekst van een toepassing zoals het simuleren van grondwaterstroming of
het bewerken van beelden bijvoorbeeld verkregen via een MRI-scanner.
Zowel de theoretische aspecten als de
praktische, software-gerelateerde aspecten komen aan de orde. Elke week is
er een hoorcollege gevolgd door een werkcollege of computerpracticum. Dit
vak is een goede orientatie op een eventuele master scientific computing en
geeft een breed beeld van het vakgebied. De relatie met de praktijk wordt
mede vormgegeven door een of meerdere gastdocenten.
Doelgroep
Studenten wiskunde of natuurkunde met belangstelling voor numerieke methoden
en computersimulaties.
Voorkennis
Lineaire algebra A (WISB121),
Lineaire algebra B (WISB122),
Infinitesimaalrekening A (WISB132),
Infinitesimaalrekening B (WISB133),
Het vak numerieke wiskunde WISB251, of het gelijktijdig volgen ervan is gewenst.
Bij twijfel, of een andere vooropleiding dan wiskunde of natuurkunde,
graag overleg met een van de docenten.
Tijdschema
We volgen ruwweg het volgende schema. "H5" betekent hoofdstuk 5 uit het boek van O'Leary.
- Moduul 1. Sept/okt. module over iteratieve oplosmethoden met toepassing in de modellering van grondwaterstroming (Sleijpen),
- Moduul 2. Okt/nov. Dichte lineaire algebra, met toepassingen (H5, 7, 8, Bisseling)
- Moduul 3. Dec. MRI-beeldverwerking gegeven door Alessandro Sbrizzi van het UMC.
Literatuur
-
Sept, Dec eigen materiaal, wordt verstrekt
-
Okt, Nov het boek van Diane O'Leary,
Scientific Computing with case studies te verkrijgen bij de boekhandel
of rechtstreeks bij SIAM met 30% korting.
Docenten
Rob Bisseling,
Gerard Sleijpen,
en gastdocent Alessandro Sbrizzi van het UMC.
Assistent
Ian Zwaan (I.N.Zwaan@uu.nl)
Tentaminering
Door middel van drie verslagen, die ieder even zwaar mee tellen
in het eindcijfer van het vak.
Studiepunten
7,5 ECTS
Eerste moduul: Grondwaterstroming
Het materiaal dat je hieronder via links kunt
ophalen en het schema is, voor de dagen die
nog niet geweest zijn, van de cursus van vorig jaar. Het materiaal dat we
daadwerkelijk zullen gebruiken en het schema dat we zullen volgen kan (een
beetje) anders zijn. Updates van het gebruikte materiaal
zullen beschikbaar zijn voor de betreffende
les, het schema zal na de les (binnen 24 uur) bijgewerkt worden.
Behandeld
- Dag 1:
-
inleiding Scientific Computing;
-
modeleren grondwaterstroming (Dictaat Sekties 1, 2.1,2.2);
-
discretiseren middels symmetrische eindige differenties
(Dictaat Sektie 3 (tot 3.1));
- Dag 2: (Dictaat: Hoofdstuk 4, 5, Appendix, inleiding Hoofdstuk 6)
-
van een stelsel vergelijkingen naar een matrix;
-
ijle matrices;
-
inleiding iteratieve methoden (Richardson ieteratie, local minimal residuals,
Generalized Conjugate Residuals)
- Dag 3: (Dictaat: Hoofdstuk 6 en 7 t/m 7.3)
-
GCR, GCR versus LMR (kosten per stap, aantal stappen)
-
preconditioneren
-
incomplete LU varianten (D-ILU, D-MILU, RILU)
- Dag 4:
-
Achtergrond informatie preconditioneren.
- Dag 5:
Discussies van de onderwerpen die in
verslag aan de orde zouden kunnen komen.
- Dag 6:
Wat aan de orde komt.
Te doen
- Dag 1:
-
(Eigen)aardigheden van Matlab eigen maken
-
discretiseer met symmetrische eindige differenties
(d.w.z., stel de formules op voor de koppelingscoëfficiënten
en bouw die in in de Matlab functie routine ‘Discretiseer.m’)
-
elimineer de functiewaarden op de rand
- Dag 2: (zorg ervoor dat je de opdrachten van de vorige week af hebt)
-
programmeer de discretisaties (bepaal de
koppelingscoëfficiënten uit de model
gegevens)
-
programmeer de opstelling van de matrix
(bepaal de matrix uit de koppelingscoëfficiënten)
-
programmeer GCR
(los de matrix-vector vergelijking op)
- Dag 3: (zorg ervoor dat je deze week in ieder
geval de eerste twee items af hebt)
-
Programmeer GCR
-
Programmeer het bepalen van de diagonaal voor RILU
-
Bouw de preconditioneringen in in GCR
- Dag 4:
-
Bouw de preconditioneringen in in GCR
- experimenten met de code
- Dag 5:
Code afmaken, besluiten welke discussies voor het verslag
met numerieke experimenten ondersteund zullen worden.
- Dag 6:
Numerieke experimenten voor in het verslag, aan het verslag
werken.
Inleveren.
- Code.
Voorzie je code van beknopt commentaar. Besteed in je commentaar
vooral aandacht aan de delen waar je problemen mee had en
vertel hoe je die problemen opgelost hebt.
- Lever je code in samen met het verslag.
Lever electronisch in, zet je commentaar in
file van de code achter commentaar tekens (%).
Lever je meerdere codes in, bundel dan alles, samen met een pdf
van het verslag (zip of tar-gzip).
-
Verslag. Schrijf een verslag (in latex,
lever je verslag in in pdf format). Diverse suggesties voor vragen
die je in het grondwaterverslag zou kunnen bespreken vind je in het Dictaat/handleiding.
In het verslag moet met name ingegaan worden op de effectiviteit van de
diverse keuzes. De numerieke experimenten in het verslag mogen niet slechts
illustratief zijn, maar dienen de argumentatie te ondersteunen. Uit het
verslag moet een kritische houding blijken. Een verslag mag samen met
teamgenoten geschreven worden. Individuele bijdragen moeten echter
herkenbaar zijn en iedere auteur is aanspreekbaar over het geheel. Het
verslag wordt individueel nabesproken. De toelichting die daarbij
gevraagd kan worden, beïnvoedt het eindcijfer. (Hier
vind je meer aanwijzingen bij het schrijven van het verslag.)
Lesmateriaal
- Een Matlab
tutorial is beschikbaar,
-
Introductie Matlab
-
Tekst: “(Eigen)aardigheden van Matlab”, met introductie opdrachten
(pdf);
- Code: partiële Matlab code voor een paar van de
introductie opdrachten
(M-files; zip,
tar.gz *).
-
Gronwaterstroming, verontreinigd grondwater
- Tekst: “Introductie Scientific Computing;
Grondwaterstroming” (Dictaat/handleiding;
pdf);
- Code: partiële Matlab code
voor het oplossen van grondwatervergelijkingen
(M-files, function files, folders; zip;
tar.gz;
*);
- Tekst: “Hoe bouw je een preconditioneerder
in?”
( Toelichting bij de partiële Matlab
voor de grondwatervergelijkingen; pdf)
-
Transparanten
Inleiding,
handouts
Inleiding,
-
Transparanten Les 1,
handouts les 1
-
Transparanten Les 2,
handouts les 2
-
Transparanten Les 3,
handouts les 3
-
Transparanten Les 4,
handouts les 4
Nuttige links
*
To unwrap FILE.tar.gz:
> gunzip FILE.tar.gz
> tar xvf FILE.tar
|
Tweede moduul: volle-matrix berekeningen
Behandeld
- Dag 7 (25 okt. 2011): (Boek O'Leary: Hoofdstuk 5.1 en 5.2)
-
Hoe reken je een determinant snel uit
-
Basic linear algebra subprograms (BLAS)
-
LU- en Cholesky-decompositie
-
pivoting
- Dag 8 (1 nov. 2011): (Boek O'Leary: Hoofdstuk 5.3)
-
QR-decompositie
-
QR via Givensrotaties
-
QR via Gram-Schmidt orthogonalisatie
-
Gebruik van QR voor kleinste-kwadratenmethode
- Dag 9 (15 nov. 2011): (Boek O'Leary: Hoofdstuk 5.5)
-
Eigendecompositie
-
Hessenberg reductie
-
QR iteratie
- Dag 10 (22 nov. 2011): (Boek O'Leary: Hoofdstuk 5.6)
-
Singuliere-waardedecompositie (SVD)
-
Lage-rang benadering van een matrix
- Dag 11 (29 nov. 2011): Zelf werken aan het verslag, onder begeleiding.
Te doen
- Dag 7 (25 okt. 2011):
-
Bereken de rijsommen van een matrix in MATLAB (challenge 5.1)
-
Schrijf een MATLAB programma voor Choleskydecompositie (challenge 5.4)
- Dag 8 (1 nov. 2011):
-
Bereken een Givensrotatie (challenge 5.5) en een QR-decompositie van een 2-bij-2 matrix (challenge 5.8)
met de hand.
-
Schrijf een MATLAB programma voor QR met Givensrotaties voor een speciale 4-bij-4 matrix
(challenge 5.6)
- Implementeer algoritme 5.3 in MATLAB, gebruikmakend van bestaande MATLAB componenten
en test het voor een zelfgekozen toepassing (zoals op pg. 67).
- Dag 9 (15 nov. 2011):
-
Voer stap 1 (Hessenberg reductie) uit op een n-bij-n matrix. Schrijf je eigen planerot.
Doe dit ook voor een symmetrische matrix.
-
Voer stap 2 (QR iteratie) uit. Experimenteer met een shift met gamma*I,
en onderzoek de invloed op de nauwkeurigheid.
- Maak een begin met je verslag.
De opgave luidt: kies 2 van de 5 decomposities (Cholesky, LU, QR, Eigen, SVD)
en schrijf een geheel eigen MATLAB code, behalve voor de SVD.
(Gebruik bestaande MATLAB-functies alleen ter controle, of voor de SVD.)
Schrijf een verslag van 6-8 pagina's, en voeg je programma's als een appendix toe.
Kies als testmatrices random matrices.
Probeer empirisch eigenschappen hiervan te ontdekken,
bijvoorbeeld over rang en determinant.
Je kunt verschillende bereiken voor de matrixwaarden kiezen,
bijv a[i,j] in het reele interval [0,1], gehele getallen {0,1},
gehele getallen {-1,1}, gehele getallen {0,1,...,R}.
Meet en analyseer de rekentijd van je programma.
De deadline voor het verslag is dinsdag 6 december 15.00 uur,
d.w.z. voor de start van het hoorcollege van het volgende moduul.
- Dag 10 (22 nov. 2011):
-
Bepaal de rekentijd voor het oplossen van een lineair stelsel m.b.v. de SVD (challenge 5.16).
-
Zoek een orthogonale basis voor de nulruimte en het beeld van A, waarvoor de SVD al bekend is
(challenge 5.17).
-
Werk verder aan je verslag.
- Dag 11 (29 nov. 2011): Werk zelf aan het verslag.
Het verslag van dit moduul is inmiddels nagekeken en kan worden opgehaald
op kamer 517 van het wiskundegebouw op donderdag 22 december 2011
(tot 15.30 uur) of weer vanaf 9 januari 2012.
Derde moduul: MRI-beeldverwerking
Docent: Alessandro Sbrizzi.
Contact: a.sbrizzi at umcutrecht.nl .
Tel: 088 75 50 288
Behandeld
- Dag 12 (6 dec. 2011):
-
Mathematische en fysische basis van Magnetic Resonance Imaging: nuclear spins, magnetisatie, Fourier Theorie en Fourier Transform.
-
Slides
-
de opgaven van deze week zijn: exercise 1 t/m 4 (zie Opgaven).
Plus de volgende (pen en papier): bewijs de shift theorem (slide 39) en bereken de Fourier transform van de functies f(x) = sqrt(a)f(ax) en f(x) = exp(-x^2/(2 sigma^2)). Dat is, laat zien dat regel 2 en 4 van de "Fourier Transform pairs" lijst (slide 29) gelden.
- Dag 13 (13 dec. 2011):
-
De k-space en k-space trajectories. Signaal opname en beeldverwerking in MRI. Discreet Fourier Transform. Nyquist criterium in MRI.
-
Slides
-
Opgaven, Data
- Dag 14 (20 dec. 2011):
-
Undersampling the k-space. De fold over effect. Parallel MRI. SENSE reconstructie techniek. Conditionering van de SENSE matrix.
-
Slides
-
Opgaven. De code en de data voor de opgaven zijn naar u gestuurd via email.
- Eindopdracht (deadline: 22 januari 2012):
Voor een uitgebreide behandeling van de Fourier Transform, zie: Gerard Sleijpen,
Lecture Notes on Fourier theory
Voor mooie animaties over de fysica van MRI en de beeldverwerking technieken, zie:
e-MRI
Last modified:
Tuesday, 25-Oct-2011 14:18:16 CEST