Μάθημα : Επιστημονικός Υπολογισμός (Ανοικτό Μάθημα)

Η χρήση των Η/Υ εισάγει μια νέα, τρίτη, επιστημονική μεθοδολογία (οι "κλασικές" ήταν η θεωρία και το πείραμα) που επιτρέπει πια να δούμε διαφορετικά την επίλυση των μεγάλων επιστημονικών προβλημάτων. Μια σειρά από περιπτώσεις στις οποίες η χρήση της "πειραματικής μεθοδολογίας" είναι πολύ δύσκολη ή απαγορευτική (π.χ. πολυδάπανη, επικίνδυνη, κ.λπ.) και όπου καθίσταται απαραίτητη η χρήση τεχνολογιών προσομοίωσης που εξαρτώνται άμεσα από τον επιστημονικό υπολογισμό. Πολύπλοκα προβλήματα μπορούν να αναλυθούν σε μικρότερα τα οποία ονομάζονται υπολογιστικοί πυρήνες ("computational kernels") και αντιστοιχούν σε συγκεκριμένα μαθηματικά προβλήματα. Είναι γεγονός ότι οι περισσότεροι από τους πυρήνες αναφέρονται σε προβλήματα υπολογιστικής γραμμικής άλγεβρας.

Διάφορα μοντέλα υπολογισμού χρησιμοποιούνται στη σύγχρονη επιστήμη και τεχνολογία. Στην επιστήμη των υπολογιστών ευρέως διαδεδομένο μοντέλο είναι το μοντέλο RAM. Στην ενότητα αυτή γίνεται αναφορά στις αδυναμίες του μοντέλου αυτού και γίνεται εισαγωγή στο μοντέλο ιεραρχικής μνήμης το οποίο μαζι με το αριθμητικό και το διακριτό μοντέλο (που θα εισαχθούν σε επόμενες ενότητες), θα χρησιμοποιηθούν για να σχεδιάστεί λογισμικό και να παραχθούν αλγόριθμοι και προγράμματα για τα οποία θα υπάρχει προβλέψιμη επίδοση και προβλέψιμα ή ελεγχόμενα σφάλματα στρογγύλευσης και διακριτοποίησης. Στη συνέχεια δίνεται μια πλήρης περιγραφή του μοντέλου ιεραρχικής μνήμης και εξετάζονται ορισμένες αδυναμίες της πολυπλοκότητας με βάση το πλήθος πράξεων Ω για την πρόβλεψη της επίδοσης. 

Οι βασικοί υπολογισμοί με διανύσματα και μητρώα (BLAS) αποτελούν κοινούς υπολογιστικούς πυρήνες σε μεγάλους υπολογισμούς. Οι υπολογισμοί αυτοί κατηγοριοποιούνται σε 3 κατηγορίες (BLAS-1, BLAS-2, BLAS-3). Στην ενότητα αυτή αναλύονται βασικές πράξεις που προκύτπουν από την C=C+AB (τη "μητέρα όλων των υπολογιστικών πυρήνων"), όπου A, B, C είναι βαθμωτοί/διανύσματα/μητρώα με κατάλληλα επιλεγμένες διαστάσεις, όπως: εσωτερικό γινόμενο (dot), μητρώο επί διάνυσμα (mv), μητρώο επί μητρώο (mm), ανανέωση πρώτης τάξης (ger) και axpy. Επιπλέον, μελετάτε η χρησιμότητα της πλοκαδοποίησης για την καλύτερη αξιοποίηση της (μικρής) τοπικότητας. Γίνεται αναφορά σε αλγορίθμους χαμηλής πολυπλοκότητας (Strassen και Winograd) για τον υπολογισμό του πολλαπλασιασμού μητρώο επί μητρώο. Τέλος, γίνεται αναφορά σε τεχνικές αναδόμησης κώδικα (και κυρίως βρόχων επανάληψης) που αποσκοπούν στην παραγωγή αποδοτικότερων υλοποιήσεων, όπως το ξετύλιγμα βρόχου.

Στην ενότητα αυτή γίνεται εισαγωγή στο αριθμητικό μοντέλο. Βασικό όχημα πάνω στο οποίο θα αναπτυχθεί το μοντέλο είναι το πρότυπο αριθμητικής κινητής υποδιαστολής (α.κ.υ.) της IEEE. Σύμφωνα με το μοντέλο κάθε υπολογισμός που εκτελείται στο υπολογιστικό σύστημα υπακούει στην αρχή της ακριβούς στρογγύλευσης. Βάσει αυτής της αρχής εκτιμάται το εμπρός (σχετικό ή απόλυτο) σφάλμα ενός αλγορίθμου. Πολλές φορές η εκτίμηση του εμπρός σφάλματος είναι πολύπλοκη και για αυτό χρησιμοποιείτε η πίσω ανάλυση σφάλματος. Στην πίσω ανάλυση σφάλματος γίνεται διερεύνηση της πίσω ευστάθειας ενός αλγορίθμου και εκτίμηση του πίσω (σχετικού ή απολύτου) σφάλματος. Το πίσω σφάλμα μαζί με το δείκτη κατάστασης αλγορίθμου δίνουν ένα φράγμα για το εμπρός σφάλμα. 

Ένα από τα σημαντικότερα προβλήματα στην Αριθμητική Γραμμική Άλγεβρα είναι η επίλυση γραμμικών συστημάτων. Η αποδοτική επίλυση γραμμικών συστημάτων βασίζεται στην εκμετάλλευση των ιδιοτήτων του μητρώου. Τον πιο γνωστό τρόπο επίλυσης γραμμικών συστημάτων αποτελεί η παραγοντοποίηση LU. Στην ενότητα αυτή γίνεται αναφορά στην παραγοντοποίηση αυτή και γιατί είναι σημαντικό να γίνεται οδήγηση στο μητρώο που εφαρμόζεται. Στη συνέχεια αναφέρονται τεχνικές οι οποίες αποσκοπούν στην βελτίωση της υπολογισθείσας λύσης, όπως η επαναληπτική εκλέπτυνση. Τέλος, σημαντικό μέρος της ενότητας αυτής αποτελεί η επίλυση συστημάτων, όταν το μητρώο είναι Συμμετρικό και Θετικά Ορισμένο (ΣΘΟ). Γίνεται αναφορά στον αλγόριθμο παραγοντοποίησης ΣΘΟ μητρώου, Cholesky, καθώς και σε μία επαναληπτική μέθοδο υποχώρου Krylov, γνωστή ως μέθοδος συζυγών κλίσεων (conjugate gradient). 

Στην ενότητα αυτή παρουσιάζεται μια σημαντική παραγοντοποίηση μητρώων, η QR. Βασικό στοιχείο του υπολογισμού της παραγοντοποίησης αποτελεί η εφαρμογή ορθογώνιων μετασχηματισμών στο μητρώο, έτσι ώστε να το μετασχηματίσουν σε άνω τριγωνικό. Οι ορθογώνιοι μετασχηματισμοί μπορούν να υπολογιστούν με διάφορες τεχνικές όπως η μέθοδος Gram-Schmidt, οι ανακλαστές Householder και οι περιστροφές Givens. Στην ενότητα αυτή αναλύεται ο τρόπος υπολογισμού της παραγοντοποίησης QR μέσω ανακλαστών Householder. Τέλος, γίνεται αναφορά στην επίλυση προβλημάτων ελαχίστων τετραγώνων με τη χρήση της παραγοντοποίησης QR.

Μητρώα που εμφανίζονται σε διάφορες εφαρμογές συνήθως έχουν ειδική δομή και χρήζουν ειδικής διαχείρισης. Είναι σημαντικό να γίνεται σωστή διαχείριση και εκμετάλλευση των ιδιοτήτων του μητρώου, έτσι ώστε να γίνεται αποδοτικότερος ο υπολογισμός των υπολογιστικών πυρήνων. Στην ενότητα αυτή γίνεται αναφορά στα αραιά μητρώα και τις τεχνικές για την αποθήκευσή τους (COO, CSR, CSC), όπως επίσης και σε μητρώα ζώνης και μεθόδους επίλυσης γραμμικών συστημάτων με αυτά.