next up previous contents
Next: Περιορισμοί στη Χρήση του Up: Ταχύς Μετασχηματισμός Previous: Διακριτοί Μετασχηματισμοί   Contents

Ο ΑΛΓΟΡΙΘΜΟΣ 22#22

Εκμεταλλευόμενοι συγκεκριμένες συμμετρίες και πλεονασμούς στον ορισμό του 23#23, μπορούμε να αναπτύξουμε έναν αλγόριθμο σύντομου δρόμου για να υπολογίζουμε τον 23#23 με μεγάλη αποδοτικότητα. Για να τον παρουσιάσουμε, θεωρείστε την περίπτωση 1667#1667. Από τον ορισμό του 23#23 έχουμε:


1676#1676

Καθαρογράφοντας τις τέσσερις εξισώσεις πλήρως, έχουμε


1677#1677

Παρατηρείστε στο Σχήμα 12.1 ότι


1678#1678

και ομαδοποιώντας τες ξανά, παίρνουμε τις τέσσερις εξισώσεις


1679#1679

Μπορούμε τώρα να προσέξουμε ότι ο μετασχηματισμός μπορεί να υπολογιστεί με μόνο 8 προσθέσεις/αφαιρέσεις και 6 πολλαπλασιασμούς, αντί για τις αναμενόμενες (4-1)*4 = 12 προσθέσεις και 1680#1680 πολλαπλασιασμούς. Στην πραγματικότητα, για αυτή τη μικρή περίπτωση απαιτούνται ακόμα λιγότεροι πολλαπλασιασμοί, αφού 1681#1681, αλλά προσπαθήσαμε να παρουσιάσουμε πώς λειτουργεί ο αλγόριθμος στη γενική του περίπτωση. Η βασική ιδέα είναι ότι ο υπολογισμός του 23#23 της αρχικής ακολουθίας τεσσάρων σημείων έχει μειωθεί στον υπολογισμό των 1682#1682 των δύο υπακολουθιών δύο σημείων, μία περιττή και μία άρτια. Αυτή η ιδιότητα γενικεύεται ως εξής: ο 23#23 μίας ακολουθίας 366#366 σημείων μπορεί να υπολογιστεί χωρίζοντάς την σε δύο 1683#1683 με το μισό μήκος, υπό τον όρο το 366#366 να είναι άρτιο.

Πριν εκφράσουμε και τυπικά τον γενικό αλγόριθμο 22#22, αρχικά θεωρούμε ένα συμπληρωματικό ανάπτυγμα σε τμήματα πινάκων που επιφέρει επιπρόσθετη επίγνωση του θέματος. Για ένα δοσμένο ακέραιο 366#366, ορίζουμε τον πίνακα 1684#1684 ως 1685#1685. ’ρα, για παράδειγμα,


1686#1686

Έστω ότι ο 1687#1687 είναι ο πίνακας μετάθεσης


1688#1688

και ότι ο 1689#1689 είναι ο διαγώνιος πίνακας


1690#1690

Τότε έχουμε


1691#1691

δηλ., ο 1692#1692 μπορεί να επανακαθοριστεί ώστε το κάθε μπλοκ να είναι μία διαγώνια κλιμακούμενη έκδοση του 1693#1693. Ένας τέτοιος ιεραρχικός διαχωρισμός μπορεί να επιτευχθεί σε κάθε επίπεδο, δεδομένου ότι ο αριθμός των σημείων είναι άρτιος. Γενικά, ο 1694#1694 είναι η μετάθεση που ομαδοποιεί τις άρτιες στήλες του 1695#1695 πριν από τις περιττές στήλες, και 1696#1696. Άρα, για να εφαρμόσουμε τον 1695#1695 σε μία ακολουθία μήκους 366#366, πρέπει να εφαρμόσουμε μερικά τον 1697#1697 στις άρτιες και περιττές υπακολουθίες του και να κλιμακώσουμε τα αποτελέσματα, όπου χρειάζεται, με τον 1698#1698.

Αυτή η περιοδικά επαναλαμβανόμενη προσέγγιση διαίρει-και-βασίλευε για τον υπολογισμό του 23#23 τυποποιείται στην παρακάτω έκφραση του αλγορίθμου 22#22, όπου υποθέτουμε ότι το 366#366 είναι δύναμη του δύο:


1699#1699

1700#1700
1701#1701
1072#1072
1702#1702
1703#1703
1704#1704
849#849
1705#1705
1706#1706
1707#1707
1708#1708
849#849
849#849

Σημειώνουμε τα παρακάτω σημεία σχετικά με τον προηγούμενο αλγόριθμο:

Παρά το όνομά του, ο γρήγορος μετασχηματισμός 21#21 είναι ένας αλγόριθμος, όχι ένας μετασχηματισμός. Είναι ένας συγκεκριμένος τρόπος (ή οικογένεια τρόπων) υπολογισμού του διακριτού μετασχηματισμού 21#21 ενός προϊόντος πίνακα-διανύσματος, του οποίου η άμεση εκτίμηση θα φαινόταν να απαιτεί 1712#1712 αριθμητικές διαδικασίες. Η χρήση του αλγορίθμου 22#22 ελαττώνει την εργασία μόνο στα 1710#1710 που στην πράξη δημιουργεί μία τεράστια διαφορά στο χρόνο που απαιτείται για τον μετασχηματισμό μεγάλων ακολουθιών, όπως φαίνεται στον Πίνακα 12.1.

Εξ' αιτίας της όμοιας μορφής του 23#23 και του αντίστροφού της (διαφέρουν μόνο στο πρόσημο του εκθέτη), ο αλγόριθμος 22#22 μπορεί επίσης να χρησιμοποιηθεί αποδοτικά και στον υπολογισμό του αντιστρόφου του 23#23. Αυτή η δυνατότητα να μεταφερόμαστε γρήγορα από το ένα μέρος στο άλλο ανάμεσα στο πεδίο του χρόνου και στο πεδίο της συχνότητας κάνει πιο πρακτική την εκτέλεση οποιονδήποτε υπολογισμών ή αναλύσεων που μπορεί να απαιτούνται σε οποιοδήποτε πεδίο είναι πιο αξιόπιστο ή αποδοτικό.

ΠΙΝΑΚΑΣ 12.1 Η πολυπλοκότητα του αλγορίθμου 22#22 εναντίον του πολλαπλασιασμού πίνακα-διανύσματος 1713#1713



Subsections

Manolis Vavalis 2000-03-24