Πίνακας ταινία

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

Πίνακας ταινιών

Εύρος ή πλάτης ζώνης

Επίσημα, θεωρούμε έναν πίνακα n×n A=(a_i,j ). Αν όλα τα στοιχεία του πίνακα είναι μηδέν εκτός μιας διαγωνίως οριοθετημένης ταινίας, το εύρος της οποίας καθορίζεται από τις σταθερές k₁ και k₂:

$a_{i,j}=0\quad {\mbox{if}}\quad j<i-k_{1}\quad {\mbox{ or }}\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.\,$

τότε οι ποσότητες k₁ και k₂ ονομάζονται κατώτερο εύρος ταινίας και ανώτερο εύρος ζώνης, αντίστοιχα Το εύρος ζώνης (bandwidth) του πίνακα είναι το μέγιστο των k₁ και k₂- με άλλα λόγια, είναι ο αριθμός k τέτοιος ώστε $a_{i,j}=0$ αν $|i-j|>k$.

Παραδείγματα

• Ένας πίνακας ταινία με k₁ = k₂ = 0 είναι ένας διαγώνιος πίνακας
• Ένας πίνακας ταινία με k₁ = k₂ = 1 είναι ένας τριγωνικός πίνακας
• Για k₁ = k₂ = 2 έχουμε έναν πενταδιαγώνιο πίνακα κ.ο.κ.
• Τριγωνικοί πίνακες
  • Για k₁ = 0, k₂ = n−1, προκύπτει ο ορισμός ενός άνω τριγωνικού πίνακα
  • Ομοίως, για k₁ = n−1, k₂ = 0 προκύπτει ένας κάτω τριγωνικός πίνακας.
• Ανώτεροι και κατώτεροι πίνακες Έσενμπεργκ
• Πίνακες Τόεπλιτς όταν το εύρος ζώνης είναι περιορισμένο.
• Διαγώνιοι Σύνθετοι πίνακες
• Πίνακες μετατόπισης και πίνακες διάτμησης
• Πίνακες στην κανονική μορφή του Ζορντάν
• Πίνακας skyline, που ονομάζεται επίσης «πίνακας μεταβλητής ταινίας» - μια γενίκευση του πίνακα ταινίας
• Οι αντίστροφοι των πινάκων Λέμερ είναι σταθεροί τριαδιαγώνιοι πίνακες, και επομένως είναι πίνακες ζώνης.

Εφαρμογές

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

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

Αποθήκευση ταινίας

Οι πίνακες ταινιών αποθηκεύονται συνήθως με την αποθήκευση των διαγωνίων στη ζώνη- οι υπόλοιποι είναι σιωπηρά μηδενικοί.

Παραδείγματος χάριν, ένας τριδιαγώνιος πίνακας έχει εύρος ζώνης 1. Ο πίνακας 6 επί 6

${\begin{bmatrix}B_{11}&B_{12}&0&\cdots &\cdots &0\\B_{21}&B_{22}&B_{23}&\ddots &\ddots &\vdots \\0&B_{32}&B_{33}&B_{34}&\ddots &\vdots \\\vdots &\ddots &B_{43}&B_{44}&B_{45}&0\\\vdots &\ddots &\ddots &B_{54}&B_{55}&B_{56}\\0&\cdots &\cdots &0&B_{65}&B_{66}\end{bmatrix}}$

αποθηκεύεται ως ο πίνακας 6 επί 3

${\begin{bmatrix}0&B_{11}&B_{12}\\B_{21}&B_{22}&B_{23}\\B_{32}&B_{33}&B_{34}\\B_{43}&B_{44}&B_{45}\\B_{54}&B_{55}&B_{56}\\B_{65}&B_{66}&0\end{bmatrix}}.$

Μια περαιτέρω εξοικονόμηση είναι δυνατή όταν ο πίνακας είναι συμμετρικός. Παραδείγματος χάριν, ας θεωρήσουμε έναν συμμετρικό πίνακα 6 επί 6 με ανώτερο εύρος ζώνης 2:

${\begin{bmatrix}A_{11}&A_{12}&A_{13}&0&\cdots &0\\&A_{22}&A_{23}&A_{24}&\ddots &\vdots \\&&A_{33}&A_{34}&A_{35}&0\\&&&A_{44}&A_{45}&A_{46}\\&sym&&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}.$

Αυτός ο πίνακας αποθηκεύεται ως πίνακας 6 επί 3:

${\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{22}&A_{23}&A_{24}\\A_{33}&A_{34}&A_{35}\\A_{44}&A_{45}&A_{46}\\A_{55}&A_{56}&0\\A_{66}&0&0\end{bmatrix}}.$

Μορφή ταινίας αραιών πινάκων

Από υπολογιστική άποψη, η εργασία με πίνακες ταινίας είναι πάντα προτιμότερη από την εργασία με τετραγωνικούς πίνακες παρόμοιας διάστασης. Ένας πίνακας ταινία

μπορεί να παρομοιαστεί ως προς την πολυπλοκότητα με έναν ορθογώνιο πίνακα του οποίου η διάσταση γραμμής είναι ίση με το εύρος ζώνης του πίνακα ταινίας. Έτσι, η εργασία που απαιτείται για την εκτέλεση πράξεων όπως ο πολλαπλασιασμός μειώνεται σημαντικά, οδηγώντας συχνά σε τεράστια εξοικονόμηση χρόνου υπολογισμού και πολυπλοκότητας.

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

Ο αλγόριθμος Κάθιλ-ΜακΚί (Cuthill–McKee) μπορεί να χρησιμοποιηθεί για τη μείωση του εύρους ζώνης ενός αραιού συμμετρικού πίνακα. Υπάρχουν, ωστόσο, πίνακες για τους οποίους ο αντίστροφος αλγόριθμος Κάθιλ-ΜακΚί αποδίδει καλύτερα. Υπάρχουν πολλές άλλες μέθοδοι που χρησιμοποιούνται.

Το πρόβλημα της εύρεσης μιας αναπαράστασης ενός πίνακα με ελάχιστο εύρος ζώνης μέσω μεταθέσεων των γραμμών και των στηλών είναι NP-Δύσκολα .

Δημοσιεύσεις

• Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf. 
• Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9. 
• Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244. 
• Bareiss, E. H. (1969), «Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices», Numerische Mathematik 13 (5): 404–424, doi:10.1007/BF02163269 
• Goldreich, O.; Tal, A. (2018), «Matrix rigidity of random Toeplitz matrices», Computational Complexity 27 (2): 305–350, doi:10.1007/s00037-016-0144-9 
• Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems
• Gray R. M., Toeplitz and Circulant Matrices: A Review (Now Publishers)
• Noor, F.; Morgera, S. D. (1992), «Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues», IEEE Transactions on Signal Processing 40 (8): 2093–2094, doi:10.1109/78.149978 
• Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 978-0817642402 
• Ye, Ke; Lim, Lek-Heng (2016), «Every matrix is a product of Toeplitz matrices», Foundations of Computational Mathematics 16 (3): 577–598, doi:10.1007/s10208-015-9254-z 

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Ταυτοτικός πίνακας
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Διανυσματικός χώρος
• Αντιμεταθέσιμοι πίνακες
• Πολλαπλασιασμός πινάκων
• Τριγωνικός πίνακας
• Διακριτός μετασχηματισμός Φουριέ
• Αντιστρέψιμος πίνακας
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Large Random Matrices: Lectures on Macroscopic Asymptotics: École d'Été de .....
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Random Matrices, Random Processes and Integrable Systems
• Random Matrices
• Toeplitz and Circulant Matrices: A Review

Παραπομπές

• Atkinson, Kendall E. (1989), An Introduction to Numerical Analysis, John Wiley & Sons, ISBN 0-471-62489-6 .
• Davis, Timothy A. (2006), Direct Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, ISBN 978-0-898716-13-9 .
• Feige, Uriel (2000), «Coping with the NP-Hardness of the Graph Bandwidth Problem», Algorithm Theory - SWAT 2000, Lecture Notes in Computer Science, 1851, doi:10.1007/3-540-44985-X_2 .
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd έκδοση), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.4», Numerical Recipes: The Art of Scientific Computing (3rd έκδοση), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html?pg=56, ανακτήθηκε στις 2024-08-26 .