Επιστημονικός Υπολογισμός I

ΜHYΠ 343

Χειμερινό Εξάμηνο 2012

Γενικές Πληροφορίες

• Υπεύθυνος Μαθήματος: Καθηγητής Ε. ΓΑΛΛΟΠΟΥΛΟΣ (send email). Β' κτίριο, ισόγειο (Β020)

• Διδάσκοντες: καθηγητής Ε. Γαλλόπουλος

• Επικουρικό έργο: Βασίλειος Καλαντζής, Γιώργος Δρακόπουλος, Β' κτίριο, ισόγειο (Β020), 

• Ώρες γραφείου: Ε. Γαλλόπουλος, Τετάρτη 12:00 - 13:30. Β. Καλαντζής: Τετάρτη 13:00 - 15:00, Γ. Δρακόπουλος: Τετάρτη 13:00 - 15:00 Παρασκευή 13:00-15:00. 

• Ώρες παραδόσεων και φροντιστηρίων: Δευτέρα 11:00-13:00 & Παρασκευή 9:00-11:00 (B4). ΠΡΟΣΟΧΗ - ΑΛΛΑΓΗ ΩΡΑΣ: Από τις 15/10 οι διαλέξεις της Δευτέρας προγραμματίζεται να γίνονται 15:00-17:00 στο ΒΑ.

• Ώρες εργαστηρίου: Πέμπτη 11:00-13:00 στο Υ/Κ του Τμήματος. Όταν υπάρχει χρόνος, θα γίνονται ασκήσεις και θα απαντώνται απορίες σχετικά με το μάθημα.



• Ηλεκτρονικό φόρουμ του μαθήματος στο myceid. 

• Συγγράμματα - σημειώσεις
  

  • 1) Ε. Γαλλόπουλος, "Επιστημονικός Υπολογισμός Ι", 2011.  Οι σημειώσεις θα διατίθεται από την ιστοσελίδα του μαθήματος από εδώ (με κωδικό που θα ανακοινωθεί στην 1η διάλεξη). Το βιβλίο θα διατίθεται σταδιακά.
  • 2) Cleve Moler, Αριθμητικές Μέθοδοι με το MATLAB, μετάφραση Β. Μεταφτσή, εκδ. Κλειδάριθμος. (Η αγγλική εκδοχή του βιβλίου - με τίτλο Numerical Computing with MATLAB, εκδ. SIAM, 2004 - είναι διαθέσιμη online). Το βιβλίο που πρέπει να δηλώσετε όλοι κατά την εγγραφή σας στο μάθημα. 

  • γ) Επιλεγμένες διαφάνειες διαλέξεων - πρόσβαση μέσω του ημερολογίου του μαθήματος.

• Δείτε εδώ σημαντικές πληροφορίες σχετικά με την αξιολόγηση στο μάθημα και τη βαθμολογία. 

Ανακοινώσεις: Να διαβάζονται τακτικά !

• Περισσότερες πληροφορίες και το ημερολόγιο του μαθήματος διαθέσιμες από εδώ. 

• Χρήσιμη βιβλιογραφία (πολλά είναι διαθέσιμα online, στη βιβλιοθήκη του Τμήματος, στην Κεντρική Βιβλιοθήκη ή στη βιβλιοθήκη του διδάσκοντα!)

  • E. Anderson et al., LAPACK User’ Guide, SIAM (Society of Industrial and Applied Mathematics), 3d ed. 1999 (διαθέσιμο online)

  • M. Heath, Scientific Computing: An Introductory Survey, McGraw Hill (2η έκδ. 2002) - Στη ΚΒ θα βρείτε την 1η έκδοση.

  • Dianne P. O'Leary, Scientific Computing with Case Studies, SIAM Press , 2009.

  • Σχετικά με τη MATLAB: Υπάρχουν πάρα πολλοί βιβλία και οδηγοί διαθέσιμοι από το το διαδίκτυο πέραν του βιβλίου του Cleve Moler. Σημειώνουμε όμως ότι οι παρακάτω αναφορές μπορεί να μην περιγράφουν πάντα την νεώτερη έκδοση της MATLAB.  Είναι όμως πολύ ικανοποιητικές για τις ανάγκες του μαθήματος. :  0) Οδηγίες από τη Mathworks. 1) D. Higham and N. Higham, MATLAB Guide, 2nd Edition, SIAM Press, 2005. 2) T. Davis, MATLAB Primer, 7th Edition, CRC Press. 3) Edward Neuman, Programming in MATLAB Tutorials (διαθέσιμο on-line). Κυκλοφορεί μεταφρασμένο ως βιβλίο (!!) στα Ελληνικά: Προγραμματίζοντας στο MATLAB, Σειρά Minimax, εκδ. Fountas. 4) Duane Hanselman, Bruce Littlefield, Μάθετε το MATLAB 7, τόμος Α, Κλειδάριθμος. 

• Άρθρα

  • E. Gallopoulos and A. Sameh, "CSE: Content and Product" IEEE Computational Science and Engineering Mag., pp. 39-43 (Apr.-June 1997).

  • L.N. Trefethen, Predictions for Scientific Computing 50 years from now

• Γενικές ανακοινώσεις δημοσιεύονται στο forum του μαθήματος στo myceid. 

ΠΡΟΣχέδιο διδασκαλίας (Δ = διάλεξη, Ε = εργαστήριο, Φ = φροντιστήριο) - υπό αναθεώρηση

Ο Επιστημονικός Υπολογισμός  ασχολείται με βασικά θέματα που αφορούν στην ανάπτυξη και στην αποδοτική χρήση υπολογιστικών εργαλείων που βοηθούν στην πρακτική χρήση των μαθηματικών μοντέλων της επιστήμης και της τεχνολογίας, π.χ. σε προσομοιώσεις.  Στο μάθημα αναπτύσσεται το υπόβαθρο για το  σχεδιασμό αποτελεσματικών αλγορίθμων και λογισμικού για σύγχρονες αρχιτεκτονικές Η/Υ για σημαντικά υπολογιστικά προβλήματα μεγάλης κλίμακας στηριζόμενο στην έννοια των μοντέλων (κυρίως του υπολογιστικού και αριθμητικού, με σύντομη εισαγωγή στο διακριτό μοντέλο) και στη χρήση τους για την πρόβλεψη της επίδοσης και σφάλματος σε σύγχρονους υπολογισμούς.  Συνοπτικά:  Στοιχεία που επιδρούν στην απόδοση των προγραμμάτων του EY. Μοντέλα της επιστήμης και της τεχνολογίας.  Θεωρητικά υπολογιστικά μοντέλα και μοντέλο ιεραρχικής μνήμης. Τεχνικές μετάφρασης, προφόρτωση.  Στοιχεία περιβάλλοντος MATLAB.  Εργαλεία μέτρησης επίδοσης.  Απώλεια πληροφορίας στον επιστημονικό υπολογισμό. Αριθμητικό μοντέλο και πρότυπο κινητής υποδιαστολής  IEEE. Θεωρία και εργαλεία εκτίμησης σφάλματος και ποιότητας υπολογισμών. Κατάσταση προβλήματος και αλγορίθμου.  Εμπρός και πίσω σφάλμα. Θεμελιώδη προβλήματα της αριθμητικής γραμμικής άλγεβρας. Η ιεραρχία BLAS, ορμαθοποίηση και βασικές πράξεις στο υπολογιστικό μοντέλο ιεραρχικής μνήμης. Θεωρία και πράξη στους υπερταχείς πολλαπλασιασμούς μητρώων. Αλγόριθμοι και ανάλυση σφάλματος στο υπολογιστικό και αριθμητικό μοντέλο για πράξεις υπολογιστικής γραμμικής άλγεβρας. Λογισμικό LAPACK. Μητρώα ζώνης: δομές αποθήκευσης και μέθοδοι διαχείρισής τους. Ελάχιστα τετράγωνα και υλοποιήσεις της παραγοντοποίησης QR. Διακριτό μοντέλο και βασικές μέθοδοι προσομοίωσης διαφορικών εξισώσεων. Σφάλμα διακριτοποίησης. Προβλήματα συνοριακών τιμών και προβλήματα αρχικών τιμών. 

Το παρακάτω πρόγραμμα είναι ένα προσχέδιο για τις πρώτες εβδομάδες! Πολύ πιο ακριβές (αλλά «κατόπιν εορτής»)  είναι το ημερολόγιο του μαθήματος. 

1-2η:

• Τι είναι ο Επιστημονικός Υπολογισμός. Αλγόριθμοι και εφαρμογές. Στοιχεία  που επιδρούν στην απόδοση των προγραμμάτων του EY: Αρχιτεκτονικές και λογισμικό. Η γραμμική άλγεβρα ως μέσο για την παρουσίαση των βασικών προβλημάτων του ΕΥ. Μοντέλα της επιστήμης και της τεχνολογίας. Θεωρητικά υπολογιστικά μοντέλα. Μοντέλο ιεραχικής μνήμης. Τοπικότητα. Πράξεις, μεταφορές και πολυπλοκότητα. Πράξεις DOT, sAXPY. Μέτρηση επίδοσης και απόδοσης.
• Ε/Φ: Σύγχρονα εργαλεία προγραμματισμού: Εισαγωγή στο περιβάλλον MATLAB. Προγραμματισμός και  m-functions. Εργαλεία μέτρησης επίδοσης. Διανυσματική γραφή.
• Συστάσεις για μελέτη: α) Σημειώσεις (1ο και 2ο κεφάλαιο), β) Πληροφορίες για το MATLAB. γ) Το 1ο κεφ. του βιβλίου του C. Moler. 

3η:

• Απώλεια πληροφορίας στον επιστημονικό υπολογισμό. Στοιχεία γραμμικής άλγεβρας: Νόρμες διανυσμάτων και μητρώων. Απόλυτο και σχετικό σφάλμα. Στοιχεία αριθμητικής κινητής υποδιαστολής. Το πρότυπο αριθμητικής IEEE. Η εντολή FMA. Αριθμητικές πράξεις και μετάδοση σφάλματος στρογγύλευσης.
• Ε/Φ: Παραδείγματα πράξεων α.κ.υ.
• Συστάσεις για μελέτη: α) Σημειώσεις (3ο κεφάλαιο), β) Αναφορές σχετικά με το πρότυπο IEEE, γ) σημειώσεις του M. Overton

4η:

• Στοιχεία θεωρίας και εργαλεία για την εκτίμηση σφάλματος και ποιότητα υπολογισμών. Παραγοντοποίηση ιδιαζουσών τιμών. Αντισταθμισμένη άθροιση. Υποκανονικοποίηση και χρήσεις της. Εμπρός σφάλμα. Κατάσταση προβλήματος και αλγορίθμου. Ευστάθεια αλγορίθμου. Πίσω σφάλμα.
• Ε/Φ: Παραδείγματα χρήσης των εργαλείων
• Συστάσεις για μελέτη: α) Σημειώσεις (3ο κεφάλαιο), β) Παραπομπή για την ανάλυση σφάλματος στη βιβλιοθήκη LAPACK.

5η:

• Τα θεμελιώδη προβλήματα της αριθμητικής γραμμικής άλγεβρας (ΑΓΑ). Τεχνικές μετάφρασης, προφόρτωση, Διάταξη στοιχείων στη μνήμη. Τύποι πινάκων/μητρώων.  Βασικές πράξεις της ΑΓΑ και επίδραση της ιεραρχικής μνήμης. Οι πράξεις στο υπολογιστικό μοντέλο ιεραρχικής μνήμης. Πολλαπλασιασμός μητρώων και ορμαθοποίηση.  Η ιεραρχία των BLAS (βλ. εργασίες #1.[1]). Παραδείγματα και case study (βλ. εργασίες #1.[8,9,10]). Οι πράξεις σε αριθμητική κινητής υποδιαστολής.  Υπερταχύς πολλαπλασιασμός μητρώων.

Ε/Φ: Να κατεβάσετε και να πειραματιστείτε με το Matrix Computation toolbox του N. Higham.

• Συστάσεις για μελέτη: α) Σημειώσεις (4ο κεφάλαιο), β) ιστοσελίδα των BLAS. γ) Δείτε τη σχετική σελίδα της Intel σχετικά με τη βιβλιοθήκη  BLAS, δ) Εργασία των Dayde και Duff για υλοποιήσεις των BLAS-3 (προσπελασιμη μόνον από upatras). ε) Η κλασική εργασία του Strassen "Gaussian elimination is not optimal" είναι διαθέσιμη ηλεκτρονικά από το περιοδικό Numerische Mathematik μέσω της συνδρομής της ΒΥΠ στο Historical Archive του Springer Link αλλά και εδώ.

'Αλλοι ενδιαφέροντες σύνδεσμοι και θέματα

• SIAM (Society for Industrial and Applied Mathematics) Επιστημονική εταιρεία με σημαντικές δραστηριότητες και εκδόσεις στην περιοχή του Επιστημονικού Υπολογισμού.

• Computing in Science and Engineering Magazine (CiSE)

• Numerical Analysis Digest (NA-Net): Ένα σύστημα επικοινωνίας και ανταλλαγής απόψεων για τους ερευνητές του Επιστημονικού Υπολογισμού και συναφών πεδίων.

• Survival Guide for Scientific Computing! Χρήσιμη ιστοσελίδα της Καθηγήτριας Dianne O'Leary (University of Maryland).

Ημερομηνία ανανέωσης 29/09/11