Ξεχάσατε τον κωδικό σας?
Μέθοδοι Αραιής Παραγοντοποίησης
Document Actions
Next: Ταχύς Μετασχηματισμός Up: ¶ΜΕΣΕΣ ΜΕΘΟΔΟΙ ΓΙΑ ΑΡΑΙΑ Previous: ¶ΜΕΣΕΣ ΜΕΘΟΔΟΙ ΓΙΑ ΑΡΑΙΑ Contents
Μέθοδοι Αραιής Παραγοντοποίησης
Η απαλοιφή 1#1 και οι παραλλαγές της όπως η παραγοντοποίηση 883#883 για συμμετρικούς θετικά ορισμένους πίνακες είναι εφαρμόσιμες στην επίλυση μεγάλων αραιών συστημάτων, αλλά πρέπει να προσέξουμε πολύ για να επιτύχουμε μία ικανοποιητική απόδοση τόσο στο χρόνο επίλυσης όσο και στις απαιτήσεις αποθηκευτικού χώρου. Το κλειδί για αυτή την απόδοση είναι να αποθηκεύουμε και να εργαζόμαστε μόνο στις μη μηδενικές καταχωρήσεις του πίνακα. Άρα, απαιτούνται ειδικές δομές δεδομένων αντί για τους απλούς δισδιάστατους πίνακες που είναι τόσο απλοί για να αποθηκεύουν τόνο πυκνούς πίνακες.
Για προβλήματα στη μία διάσταση, οι εξισώσεις και οι άγνωστοι μπορούν συνήθως να ταξινομηθούν έτσι ώστε τα μη μηδενικά στοιχεία να είναι συγκεντρωμένα σε μία σχετικά στενή ζώνη, η οποία μπορεί να αποθηκευτεί αποτελεσματικά σε έναν ορθογώνιο δισδιάστατο πίνακα μέσω των διαγωνίων. Είναι διαθέσιμοι αλγόριθμοι για τη μείωση του εύρους της ζώνης, αν είναι απαραίτητο, επαναταξινομώντας τις γραμμές και τις στήλες ενός πίνακα. Αλλά για προβλήματα στις δύο ή στις τρεις διαστάσεις, ακόμα και η όσο το δυνατόν πιο στενή ζώνη συχνά περιέχει κυρίως μηδενικά, και άρα κάθε τύπος αποθήκευσης δισδιάστατου πίνακα θα μπορούσε να είναι απαγορευτικά πολυέξοδος. Γενικά, τα αραιά συστήματα απαιτούν δομές δεδομένων στις οποίες αποθηκεύονται ξεχωριστές μη μηδενικές καταχωρήσεις, μαζί με τους δείκτες που απαιτούνται για να προσδιορίζουν τις θέσεις τους στον πίνακα. Η έμμεση αποθήκευση των δεικτών δεν προκαλεί μόνο υπερχείλιση αποθηκευτικού χώρου αλλά κάνει επίσης και τις αριθμητικές εφαρμογές επί των μη μηδενικών στοιχείων λιγότερο αποτελεσματικές εξαιτίας της έμμεσης διευθυνσιοδότησης που απαιτείται για να προσπελάσουμε τους τελεστέους. Άρα, μία τέτοια αναπαράσταση αξίζει τον κόπο μόνο αν ο πίνακας είναι ικανοποιητικά αραιός, που είναι συχνά το θέμα πολύ μεγάλων προβλημάτων που προκύπτουν από τις ΜΔΕ και πολλές άλλες εφαρμογές.
Όταν εφαρμόζεται σε έναν αραιό πίνακα, η παραγοντοποίηση 2#2 ή η 883#883 μπορεί να έρθει σε πέρας με τον συνηθισμένο τρόπο, αλλά το να πάρουμε γραμμικούς συνδυασμούς των γραμμών ή των στηλών για να εξαφανίσουμε ανεπιθύμητες μη μηδενικές καταχωρήσεις μπορεί διαδοχικά να εισάγει νέα μη μηδενικά στοιχεία σε περιοχές του πίνακα που αρχικά ήταν μηδέν. Τέτοια νέα μη μηδενικά στοιχεία, που λέγονται γεμίσματα, πρέπει τότε να αποθηκευτούν και, ανάλογα με τις θέσεις τους, μπορεί τελικά να εξαφανιστούν και αυτά προκειμένου να πάρουμε τους τριγωνικούς παράγοντες. Σε κάθε περίπτωση, μπορούμε να περιμένουμε οι τριγωνικοί παράγοντες στους οποίους καταλήγουμε να περιέχουν τουλάχιστον τόσα μη μηδενικά στοιχεία όσα και ο αρχικός πίνακας και συνήθως και ένα μεγάλο μέρος από γεμίσματα. Το πλήθος των γεμισμάτων που προέκυψαν είναι πολύ ευαίσθητο στη σειρά με την οποία εξελίχθηκαν οι γραμμές και οι στήλες του πίνακα, οπότε ένα από τα κεντρικά προβλήματα κατά την αραιή παραγοντοποίηση είναι να επαναδιατάξουμε τον αρχικό πίνακα για να περιορίσουμε το μέγεθος των γεμισμάτων από το οποίο πάσχει ο πίνακας κατά την παραγοντοποίηση. Η ακριβής ελαχιστοποίηση των γεμισμάτων καταλήγει να είναι ένα πολύ δύσκολο συνδυαστικό πρόβλημα (1660#1660-πλήρες), αλλά είναι διαθέσιμοι οι ευρετικοί αλγόριθμοι, όπως οι αλγόριθμοι ελάχιστου βαθμού και φωλιασμένης ανατομής, οι οποίοι κάνουν καλή δουλειά στην ελαχιστοποίηση των γεμισμάτων για πολλούς τύπους προβλημάτων. Σκιαγραφούμε εν συντομία αυτούς τους αλγορίθμους στο παρακάτω παράδειγμα. Δείτε το [68,93] για περισσότερες λεπτομέρειες.
Ο μη μηδενικός τύπος του 1662#1662 συμμετρικού θετικά ορισμένου πίνακα Α αυτού του γραμμικού συστήματος φαίνεται στο κέντρο του Σχήματος 11.6, όπου μία μη μηδενική καταχώρηση του πίνακα σημειώνεται με Χ και οι μηδενικές καταχωρήσεις είναι κενές. Οι διαγώνιες καταχωρήσεις του πίνακα αντιστοιχούν στους κόμβους της διαμέρισης, και οι μη μηδενικές καταχωρήσεις εκτός της διαγωνίου αντιστοιχούν στις κορυφές της διαμέρισης (δηλ., 1663#1663 οι κόμβοι 824#824 και 573#573 είναι γειτονικοί). Παρατηρείστε ότι ο πίνακας έχει τη μορφή ταινίας, αλλά έχει και πολλές μηδενικές καταχωρήσεις μέσα στην ταινία. Πιο συγκεκριμένα, ο πίνακας είναι μπλοκ τριδιαγώνιος, με το κάθε μη μηδενικό μπλοκ να είναι είτε διαγώνιο είτε τρισδιαγώνιο, όπως θα περίμενε κανείς για μία ταξινόμηση σύμφωνα με τις γραμμές ή με τις στήλες ενός πλέγματος δύο διαστάσεων. Η παραγοντοποίηση 883#883 του πίνακα με αυτή την ταξινόμηση (νέα μη μηδενικά στοιχεία) συμβολίζονται με το +. Θα δούμε ότι υπάρχουν και άλλα συστήματα στα οποία ο πίνακας υποφέρει σημαντικά λιγότερο από γεμίσματα.
Το κάθε βήμα στη διαδικασία παραγοντοποίησης αντιστοιχεί στην απαλοιφή ενός κομβικού σημείου της διαμέρισης. Η απαλοιφή ενός κομβικού σημείου οδηγεί στο να συνδεθούν μεταξύ τους όλα τα γειτονικά του κομβικά σημεία. Αν οποιαδήποτε από αυτά τα γειτονικά κομβικά σημεία δεν ήταν ήδη συνδεδεμένα, τότε προκύπτει γέμισμα (δηλ., νέες κορυφές στη διαμέριση και νέα μη μηδενικά στοιχεία στον πίνακα). Άρα, μία καλή εύρεση για τον περιορισμό του γεμίσματος είναι να εξαλείψουμε πρώτα εκείνους τους κόμβους που έχουν τους λιγότερους γείτονες. Το πλήθος των γειτόνων ενός δοσμένου κόμβου λέγεται βαθμός του, οπότε αυτή η εύρεση είναι γνωστή ως ο ελάχιστος βαθμός. Στο κάθε βήμα, ο αλγόριθμος του ελαχίστου βαθμού επιλέγει να απαλείψει έναν κόμβο με μικρότερο βαθμό, σπάζοντας αυθαίρετα τους δεσμούς. Αφού έχουμε απαλείψει τον κόμβο, οι παλιοί του γείτονες συνδέονται όλοι μεταξύ τους, οπότε οι βαθμοί κάποιων κόμβων μπορεί να αλλάξουν. Στη συνέχεια επαναλαμβάνεται η διαδικασία, απαλείφοντας έναν νέο κόμβο ελάχιστου βαθμού, και αυτό συνεχίζεται μέχρι να έχουν απαλοιφεί όλοι οι κόμβοι. Μία ταξινόμηση ελαχίστου βαθμού για το πρόβλημα του παραδείγματός μας φαίνεται στο Σχήμα 11.7, μαζί με τον αντίστοιχο πίνακα αντιμετάθεσης και τον παράγοντα 883#883 που προκύπτει. Παρόλο που δεν υπάρχει κανένας προφανής τύπος για τα μη μηδενικά στοιχεία στον αναδιαταγμένο πίνακα, ο παράγοντας 883#883 υποφέρει πολύ λιγότερο από γεμίσματα από ότι με την ταινιωτή διάταξη. Αυτή η διαφορά φαίνεται πολύ πιο έντονα σε μεγαλύτερα προβλήματα, και πιο πολύπλοκες παραλλαγές του αλγορίθμου ελαχίστου βαθμού βρίσκονται ανάμεσα στους πιο αποτελεσματικούς γνωστούς αλγορίθμους ταξινόμησης γενικού σκοπού.
ΣΧΗΜΑ 11.6 Διαμερίσεις πεπερασμένων διαφορών και μη μηδενικοί τύποι του αντίστοιχου αραιού πίνακα Α και του παράγοντα 1664#1664.
ΣΧΗΜΑ 11.7 Διαμερίσεις πεπερασμένων διαφορών αναδιαταγμένες με τη μέθοδο του ελαχίστου βαθμού, με μη μηδενικούς τύπους του αντίστοιχου αραιού πίνακα αντιμετάθεσης Α και του παράγοντα 1664#1664.
ΣΧΗΜΑ 11.8
Διαμερίσεις πεπερασμένων διαφορών αναδιαταγμένες με τη μέθοδο της φωλιασμένης ανατομής, με μη μηδενικούς τύπους του αντίστοιχου αραιού πίνακα αντιμετάθεσης Α και του παράγοντα 1664#1664. Η φωλιασμένη ανατομή έχει τη στρατηγική διαίρει-και-βασίλευε για να καθορίζει μία καλή ταξινόμηση για να περιορίσει το γέμισμα κατά την αραιή παραγοντοποίηση. Αρχικά, επιλέγεται ένα μικρό σύνολο από κόμβους του οποίου η αφαίρεση χωρίζει τη διαμέριση σε δύο τμήματα σχεδόν ίσου μεγέθους, και αυτοί οι διαχωριστικοί κόμβοι αριθμούνται από το τέλος. Στη συνέχεια η διαδικασία επαναλαμβάνεται αναδρομικά στο κάθε τμήμα της διαμέρισης που απομένει μέχρι που να αριθμηθούν όλοι οι κόμβοι. Μία ταξινόμηση με τη μέθοδο της φωλιασμένης ανατομής για το πρόβλημα του παραδείγματός μας φαίνεται στο Σχήμα 11.8, μαζί με τον αντίστοιχο πίνακα αντιμετάθεσης και τον παράγοντα 883#883 που προκύπτει. Ο διαχωρισμός της διαμέρισης σε δύο τμήματα σημαίνει ότι κανένας κόμβος στο καθένα από τα δύο τμήματα δε συνδέεται με οποιονδήποτε κόμβο από το άλλο. Με άλλα λόγια, η ανατομή περιέχει μπλοκς από μηδενικά στον πίνακα (που σημειώνονται με τα τετράγωνα στο Σχήμα 11.8) τα οποία προφυλάσσονται αυτόματα κατά τη διάρκεια της παραγοντοποίησης, και άρα περιορίζονται τα γεμίσματα. Την αναδρομική φύση του αλγορίθμου μπορούμε να τη δούμε στην ιεραρχική δομή των μπλοκ του πίνακα, η οποία θα εμπλέκει πολλά ακόμα επίπεδα σε ένα μεγαλύτερο πρόβλημα.
Οι μέθοδοι αραιής παραγοντοποίησης είναι ακριβείς, αξιόπιστοι και ισχυροί. Είναι οι μέθοδοι που επιλέγονται συνήθως για προβλήματα στη μία διάσταση και είναι συνήθως ανταγωνιστικές για προβλήματα στις δύο διαστάσεις, αλλά μπορεί να είναι απαγορευτικά ακριβές τόσο στην εργασία όσο και στον αποθηκευτικό χώρο για πολύ μεγάλα προβλήματα στις τρεις διαστάσεις. Θα δούμε ότι οι επαναληπτικές μέθοδοι παρέχουν μία εφαρμόσιμη εναλλακτική λύση σε αυτές τις περιπτώσεις.
Manolis Vavalis 2000-03-24
