Δημοσιεύτηκε: 24 Απρ 2010, 13:28
από Dimitris
Μιας και υπάρχουν πολλοί οδηγοί στο forum για προγραμματισμό σε διάφορες γλώσσες, με διάφορες βιβλιοθηκές (Gtk/Qt) και μιας και βαριέμαι για άλλη φορά, είπα να γράψω και έναν οδηγό πιο εξειδικευμένο. Το θέμα αυτού το νήματος είναι οι αριθμητικές μέθοδοι και υλοποίησή τους σε γλώσσες προγραμματισμού. Δεν είναι ένας παραδοσιακός οδηγός (ίσως να πρέπει να αλλαχτεί ενότητα) αλλά έχει ως σκοπό να πληροφορήσει τους ενδιαφερόμενους χρήστες για τις δυνατότητες που υπάρχουν εκεί έξω.

Το πρώτο κεφάλαιο των περισσότερων βιβλίων για αριθμητικές μεθόδους είναι η επίλυση συστημάτων γραμμικών εξισώσεων. Υπάρχουν πάρα πολλές μέθοδοι και δε θα τις σχολιάσω. Το σημαντικό είναι ότι τις περισσότερες φορές η υλοποίηση των μεθόδων, αν δεν γίνεται για εκπαιδευτικούς σκοπούς, υπόκειται σε λάθη και είναι σίγουρα αργή. Για το λόγο αυτό υπάρχει διάφορες βιβλιοθήκες. Μια από αυτές, η πλέον διαδεδομένη, είναι η LAPACK (Linear Algebra PACKage)
http://www.netlib.org/lapack/
Μη βιαστείτε να τη μεταγλωττίσετε. Υπάρχει στα αποθετήρια. Κι ακόμη καλύτερα ως ATLAS (Automatically Tuned LA Software) βελτιστοποιημένη για την εκάστοτε αρχιτεκτονική.

Κάνοντας ένα βήμα πίσω όμως, θα δούμε ότι πολλές φορές χρειάζεται πολλαπλασιασμός διανύσματος με διάνυσμα, διανύσματος με πίνακα, και πίνακα με πίνακα. Για τις πράξεις αυτές υπάρχουν επίσης βελτιστοποιημένες βιβλιοθηκες, η BLAS (Basic Linear Algebra Subprograms), με loop unrolling που χωράει στην cache κλπ. Οποτε αν χρειάζεστε τις ανωτέρω πράξεις χρησιμοποιείστε τη BLAS.
http://www.netlib.org/blas/
Μια σημείωση μόνο. Αν χρειάζεστε να κάνετε πολλούς πολλαπλασιασμούς πινακών επί πινάκων---είναι από τους πιο αργούς αλγοριθμους που υπάρχει---ξανασκεφτείτε το σχεδιασμό του προγράμματός σας.

Φυσικά για πάρα πολλές αριθμητικές μεθόδους υπάρχουν ελεύθερες βιβλιοθήκες. Μερικά παραδείγματα:
  • Μη γραμμικές εξισώσεις και προβλήματα ελαχίστων τετραγώνων είναι η minpack: http://www.netlib.org/minpack/
  • Για επίλυση κανονικών διαφορικών εξισώσεων μια αρκετά στιβαρή βιβλιοθήκη είναι η odepack: http://www.netlib.org/odepack/ Χρησιμοποιείται και από το octave.
  • Μετασχηματισμός Fourier: http://www.netlib.org/fftpack/
  • Καμπύλες Bezier, splines γραμμένη από τον ίδιο τον de Boor: http://www.netlib.org/pppack/
Όπως θα παρατηρήσατε οι παραπάνω κώδικες φιλοξενούνται στην ιστοσελίδα http://www.netlib.org η οποία είναι μια τεράστια βάση. Απόλαυση να ψάχνεις.

Φυσικά δεν πρέπει να ξεχνάμε τη GNU βιβλιοθήκη http://www.gnu.org/software/gsl/ η οποία κάνει (σχεδόν) τα πάντα και συμφέρει (μιας και είναι δωρεάν)

Παιρνόντας στις μερικές διαφορικές εξισώσεις το τοπίο δυσκολεύει. Καταρχήν χρειάζεται να δημιουργηθεί το πλέγμα. Γι'αυτή τη δουλειά υπάρχουν τα gmsh και netgen. Μετά χρειάζονται οι βιβλιοθήκες για πεπερασμένους όγκους ή πεπερασμένα στοιχεία. Ενδεικτικά μερικές είναι libmesh, getfem, dealii και φυσικά άλλα πολλά.

Βαρετά όλα αυτά; Ας δούμε κάτι διαφορετικό. Αλγοριθμική παραγώγιση. Αντί να υπολογίσουμε τις παραγώγους με το χέρι ή με πεπερασμένες διαφορές (μην το κάνετε αυτό ποτέ, το πρόβλημα είναι ill-posed) μπορούμε να χρησιμοποιήσουμε αλγοριθμική ή αυτόματη παραγώγιση. Έχουμε ένα πρόγραμμα δηλαδή το οποίο δέχεται ως δεδομένα εισόδου τον κώδικα και βγάζει ως έξοδο ένα νέο κώδικα ο οποίος είναι η παράγωγος του αρχικού ως προς κάποιες μεταβλητές. Για παράδειγμα δείτε τα ADIFOR & ADOLC για Fortran & C αντίστοιχα, όπως και το Tapenade το οποίο είναι ελεύθερη υπηρεσία δικτύου.

Για γραφικά εκτός από OpenGL και τους canvaδες του εκάστοτε GUI, υπάρχουν οι βιβλιοθήκες PLPlot για διαγράμματα και άλλα συναφή και η VTK για 3D γραφικά πιο υψηλού επιπέδου από OpenGL.

H τακτική του mixed programming, δηλαδή να μπλέκονται πολλές γλώσσες προγραμματισμού στο ίδιο πρόγραμμα, δεν είναι άσχημη όταν υπάρχουν έτοιμες οι βιβλιοθήκες και απλώς γράφεται ένας wrapper. Για παράδειγμα, οι περισσότερες βιβλιοθήκες του numpy & scipy είναι wrappers για τις παραπάνω βιβλιοθήκες που ανέφερα.

Ακόμη πιο εξειδικευμένες βιβλιοθήκες είναι η http://gmplib.org/ για αριθμητική απεριόριστης ακρίβειας.

Αυτά προς το παρόν. Οποίος ενδιαφέρεται για κάτι πιο συγκεκριμένο ας το δηλώσει και κάτι μπορεί να γίνει. :geek:

Creative Commons License
Η εργασία υπάγεται στην άδεια Creative Commons Αναφορά-Παρόμοια διανομή 3.0 Ελλάδα