Υλοποίηση της Απαλοιφής 1#1

Η απαλοιφή 1#1, ή η παραγοντοποίηση 2#2, έχει τη γενική μορφή ενός τριπλά φωλιασμένου βρόχου,

for
for
for
527#527
end
end
end

όπου οι δείκτες 528#528, 529#529 και 530#530 των βρόχων for μπορούν να ληφθούν με οποιαδήποτε σειρά, για συνολικά 531#531 διαφορετικούς τρόπους διάταξης των βρόχων. Κάποιες από τις ενδεικνυόμενες αριθμητικές πράξεις μπορούν να μεταφερθούν έξω από τον πιο εσωτερικό βρόχων για μεγαλύτερη αποτελεσματικότητα, που εξαρτάται από τους συγκεκριμένους δείκτες που εμπλέκονται και από επιπρόσθετες αναδιατάξεις των πράξεων που δεν έχουν αυστηρά φωλιασμένους βρόχους. Αυτές οι τροποποιήσεις του βασικού αλγόριθμου έχουν διαφορετικής μορφές πρόσβασης στη μνήμη (π.χ. προσπελαύνουν στη μνήμη διαμέσου γραμμών ή διαμέσου στηλών), και ακόμα διαφέρουν στην ικανότητά τους να εκμεταλλεύονται τα χαρακτηριστικά της αρχιτεκτονικής ενός συγκεκριμένου υπολογιστή (π.χ. δεδομένα αποθηκευμένα στη μνήμη, σελιδοποίηση, διανυσματοποίηση, πολυεπεξεργασία δεδομένων). Αρα, η απόδοσή τους μπορεί να ποικίλει σημαντικά σε ένα συγκεκριμένο υπολογιστή ή και σε διαφορετικούς υπολογιστές, και δεν υπάρχει μία διάταξη που να είναι υπέρτερη από όλες τις άλλες.

Πολυάριθμες λεπτομέρειες υλοποίησης του αλγόριθμου υπόκεινται σε μεταβολές αυτού του είδους. Για παράδειγμα, η διαδικασία της μερικής οδήγησης που περιγράψαμε αναζητά κατά μήκος των στηλών και εναλλάσσει τις γραμμές, αλλά εναλλακτικά θα μπορούσαμε να αναζητούμε κατά μήκος γραμμών και να εναλλάσσουμε τις στήλες. Ακόμη, έχουμε πάρει τον 107#107 να έχει μονάδες στη διαγώνιο, αλλά αντί αυτού θα μπορούσαμε να έχουμε πάρει τον 108#108 να έχει μονάδες στη διαγώνιο. Κάποιες από αυτές τις διαφορετικές υλοποιήσεις της απαλοιφής 1#1 είναι αρκετής σημασίας ώστε να τους έχουν δοθεί ονομασίες, όπως οι μέθοδοι 532#532 και 533#533.

Αν και οι πολλές δυνατές εκδοχές της απαλοιφής 1#1 μπορεί να επηρεάσουν πάρα πολύ την απόδοσή της, όλες παράγουν ουσιαστικά την ίδια παραγοντοποίηση. Με την προϋπόθεση ότι η ακολουθία των οδηγών στις γραμμές είναι η ίδια και ο πίνακας 369#369 αντιστρέψιμος , αν έχουμε δύο παραγοντοποιήσεις 2#2, 534#534 , τότε αυτή η έκφραση συνεπάγεται 535#535 είναι συγχρόνως κάτω τριγωνικός και άνω τριγωνικός πίνακας, άρα διαγώνιος. Αν οι 107#107 και 536#536 θεωρηθούν και οι δύο ως κάτω τριγωνικοί με μονάδες στην κύρια διαγώνιο, τότε ο 406#406 πρέπει να είναι ο μοναδιαίος, και άρα 537#537 και 538#538, άρα η παραγοντοποίηση είναι μοναδική. Ομως, ακόμη και χωρίς αυτή την υπόθεση, μπορούμε επίσης να συμπεράνουμε ότι η παραγοντοποίηση 2#2 είναι μοναδική εκτός από μία διαγώνιο στάθμιση των παραγόντων της. Αυτή η μοναδικότητα φαίνεται αναλυτικά στην 539#539 παραγοντοποίηση 540#540, όπου ο 107#107 είναι κάτω τριγωνικός με μονάδες στην κύρια διαγώνιο, ο 108#108 είναι άνω τριγωνικός με μονάδες στην κύρια διαγώνιο και ο 406#406 είναι διαγώνιος.

Η διαχείριση της αποθήκευσης των στοιχείων δεδομένων αποτελεί ένα άλλο σημαντικό ζήτημα της υλοποίησης. Ολοι αυτοί οι πίνακες που θεωρήσαμε - οι στοιχειώδεις πίνακες απαλοιφής 445#445, οι αντίστροφοί τους 541#541 καθώς και οι μεταθετικοί πίνακες 542#542 - απλά περιγράφουν πιο τυπικά τη διαδικασία της παραγοντοποίησης. Δε σχηματίζονται αναλυτικά σε μία πραγματική υλοποίηση του αλγόριθμου. Για την εξοικονόμηση μνήμης αποθήκευσης, οι παράγοντες 107#107 και 108#108 αποθηκεύονται στις θέσεις μνήμης του δεδομένου πίνακα 543#543 με το μετασχηματισμένο πίνακα 108#108 να καταλαμβάνει το άνω τριγωνικό μέρος του πίνακα 369#369 (συμπεριλαμβανομένης της κύριας διαγωνίου), και με τους πολλαπλασιαστές που σχηματίζουν το αυστηρά κάτω τριγωνικό μέρος του πίνακα 107#107 να καταλαμβάνουν το αυστηρά κάτω τριγωνικό μέρος του πίνακα 369#369 (που είναι τώρα μηδέν). Η διαγώνιος του πίνακα 107#107 η οποία αποτελείται από μονάδες δεν χρειάζεται να αποθηκευθεί.

Για να ελαχιστοποιήσουμε τις μετακινήσεις στοιχείων, οι εναλλαγές των γραμμών που απαιτούνται εξαιτίας της μερικής οδήγησης συνήθως δεν εκτελούνται αναλυτικά. Αντ' αυτού, οι γραμμές παραμένουν στις αρχικές τους θέσεις, και ένα βοηθητικό διάνυσμα ακέραιων μεταβλητών χρησιμοποιείται για να κρατάει τη νέα διάταξη των γραμμών. Παρατηρήστε ότι ένα και μόνο τέτοιο διάνυσμα αρκεί, διότι το τελικό αποτέλεσμα όλων των εναλλαγών γραμμών απλά μια μετάθεση των ακέραιων 544#544.