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

(Aνοιξη 2013)

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

Περληψη

    Ο ΕΥ ασχολεται με προβλματα που προκπτουν κατ την επλυση προβλημτων της Επιστμης και της Τεχνολογας με Η/Υ. Στχος εναι η κατασκευ εργαλεων αιχμς χρησιμοποιντας και διανογοντας παραπρα την επιστμη και τεχνολογα των Η/Υ. Αν εξετσει κανες που καταναλνεται ο μεγαλτερος χρνος ταν εκτελονται υπολογισμο στην επιστμη και τεχνολογα, συνθως ανακαλπτει ναν υπολογιστικ πυρνα που αντιστοιχε σε πρβλημα απ την αριθμητικ γραμμικ λγεβρα. Με αυτ το σκεπτικ, στο μθημα ΕΥ-Ι αναπτξαμε το κατλληλο υπβαθρο για το σχεδιασμ αποτελεσματικν αλγορθμων και λογισμικο για μερικ γνριμα προβλματα της περιοχς. Εισαγγαμε την ννοια του αριθμητικο μοντλου καθς και του μοντλου υπολογισμο που να επιτρπουν τους σχεδιασμος αυτος. Ειδικτερα για το αριθμητικ μοντλο, εξετσαμε τρπους για την ανλυση και πρβλεψη του σφλματος που δημιουργεται κατ τη διρκεια των υπολογισμν λγω της αριθμητικς κινητς υποδιαστολς.

    Στον ΕΥ-ΙΙ:

    Θα εξετσουμε ορισμνες μεθδους προσγγισης με εφαρμογ στην επλυση προβλημτων ελαχστων τετραγνων. Θα ξαναεπισκεφθομε το 7ο κεφλαιο του ΕΥΙ και θα δομε και πλι ορισμνα θματα που χουν μεγλη σημασα στις εφαρμογς πως η ΟΚ Gram-Schmidt. Στη συνχεια θα παρουσισουμε βασικ θεωρματα της γραμμικς λγεβρας που θα μας επιτρψουν να προχωρσουμε στην κατασκευ μεθδων για την επλυση του προβλματος των ιδιοτιμν και ιδιαζουσν τιμν. Στη συνχεια θα δομε τι στις περισστερες περιπτσεις τα προκπτοντα γραμμικ προβλματα που πρπει να λσουμε εναι τσο μεγλα που δεν επιτρπουν τη χρση μεθδων σαν αυτς που μθαμε στο ΕΥ-Ι και που περιλαμβνονται σε σγχρονα πακτα πως η LAPACK και απαιτον τη χρση επαναληπτικν μεθδων. Η χρση των μεθδων αυτν οδηγε σε σφλματα προσγγισης που πρπει επσης να λβουμε υπψη μας ταν εξετζουμε την ποιτητα των αποτελεσμτων. Η κατασκευ αποτελεσματικο λογισμικο για την επλυση των προβλημτων αυτν απαιτε ειδικς μεθδους και δομς για την αναπαρσταση των αραιν μητρων. Θα εξετσουμε μερικ απ αυτ τα θματα της τεχνολογας αραιν μητρων. Σε πολλς περιπτσεις, η αποτελεσματικτητα των μεθδων μεγαλνει σημαντικ αν χρησιμοποισουμε πληροφορες απ το αρχικ φυσικ πρβλημα αν κνουμε ειδικος μετασχηματισμος. Αυτ εναι το θμα της προετοιμασας προρθμισης. πως εδαμε στον ΕΥ-Ι, μερικς φορς τα μητρα που προκπτουν (εναι μεν πυκν αλλ) χουν ειδικ δομ που τα χαρακτηρζει με λιγτερα απ n*n στοιχεα. Στις περιπτσεις αυτς, αποκτ ενδιαφρον να δομε αν μπορομε να χρησιμοποισουμε ειδικς μεθδους για τη διαχερισ τους. Θα παρουσισουμε εφαρμογς και ειδικτερα στην ανκτηση πληροφορας και στο page rank. Μια σημαντικ κατηγορα προβλημτων αυτο του τπου εναι το πρβλημα των ιδιοτιμν καθς και το πρβλημα ιδιαζουσν τιμν.
    Θα εξετσουμε επσης το πρβλημα της δισπασης σε ιδιζουσες τιμς (SVD) που χρησιμοποιεται εκτενς στο Information Retrieval.

     

    Σχδιο Επιστημονικο Υπολογισμο ΙΙ

Υπολογιστικ προβλματα μεγλης κλμακας: Απ τις Διαφορικς Εξισσεις στα Αλγοριθμικ προβλματα στο Διαδκτυο και στην Ανκτηση Πληροφορας. Δομ και ιδιαιτερτητες μεγλων υπολογιστικν προβλημτων. Επιλογ απ τα παρακτω θματα (η ακριβς επιλογ καθορζεται μετ απ συνεργασα με τους φοιτητς σντομα μετ την ναρξη της διδασκαλας): Στοιχεα θεωρας προσεγγσεων και ορθογωνων πολυωνμων. Διασπσεις μητρων και μθοδοι ανανωσης. Τεχνολογα αραιν μητρων: Μθοδοι αποθκευσης και αναπαρστασης, σχσεις με την γραφοθεωρα, η περπτωση της MATLAB. Επλυση μεγλων γραμμικν συστημτων: μεσες μθοδοι. Επισκπηση κλασικν επαναληπτικν μεθδων (Jacobi, Gauss-Seidel, SOR). Πολυωνυμικς μθοδοι επιτχυνσης (ημιεπαναληπτικ μθοδος Chebyshev). Στοιχεα μεθδων προβολς. Ορθοκανονικοποηση Gram-Schmidt στο μοντλο αριθμητικς κινητς υποδιαστολς. Υπχωροι Krylov και διαδικασα Arnoldi. Αντιπροσωπευτικς μθοδοι Krylov (FOM, GMRES, συμμετρικ Lanczos, μη συμμετρικ Lanczos, BiCG). Το πρβλημα της επανεκκνησης. Στοιχεα θεωρας και αλγριθμοι υπολογισμο ιδιοζευγν: Μθοδος δυνμεων και παραλλαγς, μθοδος QR. Μθοδοι προβολς και υπολογισμς της δισπασης ιδιαζουσν τιμν. Προσγγιση συναρτσεων μητρων με μφαση στο εκθετικ. Μητρα με ειδικ δομ (Vandermonde, Toeplitz, Hankel, μη αρνητικ, ημιδιαχωρσημα). Στοιχεα πολυπλεγματικν μεθδων. Μθοδοι πολυπλων. Αλληλεπδραση και συνργεια αρχιτεκτονικς και λογισμικο στο σχεδιασμ και υλοποηση αποτελεσματικν και ολοκληρωμνων μεθδων επλυσης προβλημτων επιστημονικο υπολογισμο. Σγχρονες βιβλιοθκες και περιβλλοντα επλυσης προβλημτων επιστημονικο υπολογισμο. Εφαρμογς στην Ανκτηση Πληροφορας και στην Ταξινμηση Ιστοσελδων.

    Παρατρηση

    Για να αξιολογσει κανες την αλγοριθμικ σημασα των θεμτων που θα συζητηθον στον ΕΥ-ΙΙ, σημεινουμε τι νας πρσφατος κατλογος που συνταξε το περιοδικ IEEE Computing in Science and Engineering Magazine με τους Top 10 Algorithms of the Century, περιλμβανε τους εξς: Ο αναγνστης μπορε να βρε τα σημεα εκενα που εναι κοιν με τον παραπνω κατλογο!

    Online Πληροφορες & Πηγς

    Βιβλιογραφα

    Πραν των σημεισεων που θα αναρτηθον εδ, σημεινουμε ορισμνες πηγς που θα χρησιμοποισουμε αρκετ κατ τη διρκεια του μαθματος. Σε μερικς περιπτσεις, το υλικ εναι διαθσιμο on-line. Σε αγκλες εναι η συντομογραφα που θα χρησιμοπεται για αναφορ στις σημεισεις καθς και σνδεσμος με τη βιβλιοθκη του Πανεπιστημου Πατρν. 
  1. [Saad.03] Y. Saad, Iterative methods for sparse linear systems, SIAM, 2003. Η 1η κδοση του βιβλου υπρχει και εδ.
  2. [Trefethen.Bau.98] N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1998.
  3. [Langville.Meyer.06] A. Langville and C. Meyer, Google's PageRank and Beyond, Princeton UP, 2006.
  4. [Elden.07] Lars Elden, Matrix Methods in Data Mining and Pattern Recognition, SIAM, 2007.
  5. [Eriksson.etal.96] K. Eriksson, D. Estep, P. Hansbo and C. Johnsson, Computational Differential Equations, Cambridge University Press, 1996. Δετε και εδ.
    [Demmel.98]  J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1998.
  6. [Pironneau.98] Introduction to Scientific Computing, Wiley, Chichester, 1998. Χρησιμοποιε το FreeFEM+.
  7. [Iserles.96] A. Iserles, A First Course in Numerical Analysis of Differential Equations, Cambridge University Press, 1996.
  8. [Templates.94] R. Barrett et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia 1994. Περιχονται και κδικες σε Matlab.
  9. [Golub.VanLoan.96] G.H. Golub and C. Van Loan, Matrix Computations, 3d Edition, Johns Hopkins University Press, 1996.
  10. [Heath.96] M. Heath, Scientific Computing: An Introductory Survey, McGraw Hill (2η κδ. 2002) - Στη ΚΒ θα βρετε την 1η κδοση.
  11. [Ueberhuber.97] C.W. Ueberhuber, Numerical Computation: Methods, software and analysis, Springer-Verlag, Berlin (1997).
Πηγς στο WWW
Γρω απ τον επιστημονικ υπολογισμ
  • E. Gallopoulos and A. Sameh, "CSE: Content and Product" IEEE Computational Science and Engineering Mag., pp. 39-43 (Apr.-June 1997).
  • Μα ενδιαφρουσα υλοποηση στο Chalmers Institute of Technology (Σουηδα)
  • L.N. Trefethen, Predictions for Scientific Computing 50 years from now
  • Επλυση ΜΔΕ: Ταχες ελλειπτικο επιλυτς. Το PDE Toolbox της MATLAB περιχει επιλυτ βασισμνο στη μθοδο ανλυσης μητρου. Πολλ βιβλα του Επιστημονικο Υπολογισμο αναφρονται σε ταχες ελλειπτικος επιλυτς. Για λεπτομερες περιγραφς των μεθδων παραπμπουμε στις σχετικς αναφορς της βιβλιογραφας των σημεισεων και ιδιατερα τα [BuGN70,Henr84, Schu77, Swar77, SwSw79, Hock65]. Η εργασα [SwSw79] αποτελε και τη βση του πολυχρησιμοποιημνου πακτου FISHPAK. Μια εκτενς βιβλιογραφικ ανασκπηση παρουσιζω στο ell.html
  • MLTemplate: Οι κδικες των [Templates.94] σε MATLAB. Προσοχ: Αρκετο απ τους κδικες αυτος χουν ξεπεραστε απ τους επαναληπτικος επιλυτς που προσφρονται πλον μαζ με τη MATLAB.
λλοι ενδιαφροντες σνδεσμοι και θματα
  • SIAM (Society for Industrial and Applied Mathematics) Επιστημονικ εταιρεα με σημαντικς δραστηριτητες και εκδσεις στην περιοχ του Επιστημονικο Υπολογισμο.
  • IEEE Computational Science and Engineering magazine/Computers in Physics: κδοση της ΙΕΕΕ σχετικ με την περιοχ.
  • Scientific Discovery through Advanced Computing Home.

  • Ημερομηνα ανανωσης: 2/10/2010