Επιστημονικός Υπολογισμός — Ιούνιος 2024¶

Μεταγραφή από τα αρχεία: 2024___1-3.jpg, 2024___4_.jpg, 2024___5.1-2.jpg, 2024___5.3.jpg, IMG_0171.png, IMG_0173.png, 2025-01-27_15.39.53.png.

2024___1-3.jpg¶

Ερώτηση 1 ♣ (20β), Χ.Ε. Μαυρίστε ή σημειώστε Χ στο κουτάκι όσα από τα παρακάτω υποερωτήματα ισχύουν στη γενική περίπτωση (εκτός αν δηλώνεται κάτι διαφορετικό). Δεν υπάρχει αρνητική βαθμολογία. Προσοχή: Για να βαθμολογηθούν, 2 από τα υποερωτήματα που θα επιλέξετε εσείς, θα χρειαστούν και αιτιολόγηση (δείτε το επόμενο ερώτημα).

[ ] Δοθέντων $A \in \mathbb{R}^{n \times n}$ και $b \in \mathbb{R}^n$, αν $A = A^\top$ και μπορούμε να εφαρμόσουμε τη διαδικασία Arnoldi για $2 < m \ll n$ βήματα για την παραγωγή ορθοκανονικής βάσης $V_m$ και του μητρώου των συντελεστών $H_m$ για τον υπόχωρο $K_m(A; e_1)$ όπου $e_1$ είναι το πρώτο διάνυσμα της τυπικής βάσης για τον $\mathbb{R}^n$, τότε θα ισχύει ότι η πρώτη στήλη του $V_m$ θα είναι το $e_1$.
[ ] Αν n=1000+randi(1000,1); D=diag(rand(n,1)); u=randn(n,1); v=u.*u;, τότε $u^\top (D+uv^\top)^{-1}v$ μπορεί να υπολογιστεί σε $\mathcal{O}(n)$ πράξεις.
[ ] Όλα τα στοιχεία του γινομένου $C = AB$ δύο $n \times n$ μητρώων $A, B$ περιέχονται στα στοιχεία του γινομένου Kronecker $\otimes B$.
[ ] Όλα τα προτεινόμενα είναι σωστά.
[ ] Κανένα από τα προτεινόμενα δεν είναι σωστά.
[ ] Στο πρότυπο IEEE α.κ.υ., αν προσθέσουμε δύο α.κ.υ. και το άθροισμα δεν είναι Inf, το σφάλμα στρογγύλευσης είναι α.κ.υ. και μπορεί να υπολογιστεί.

Ερώτηση 2 (10β) Στο προηγούμενο ερώτημα, επιλέξτε ακριβώς 2 υποερωτήματα που απαντήσατε καλύτερα και σημειώστε τους λατ. αριθμούς I, II αριστερά από το αντίστοιχο κουτάκι. και αιτιολογήστε τα σύντομα παρακάτω. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα ληφθούν υπόψη. Αν έχετε επιλέξει ότι είναι όλα σωστά ή όλα λάθος, τότε πρέπει να επιλέξετε 2 από τις ερωτήσεις που δεν είναι του τύπου όλα σωστά ή όλα λάθος και να τις απαντήσετε. Προσοχή: Μην επιχειρήσετε να αιτιολογήσετε περισσότερες ερωτήσεις γιατί δεν θα ληφθούν υπόψη. ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. I (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):

ΑΠΑΝΤΗΣΗ ΥΠΟΕΡ. II (σημειώστε ποιο είναι στην προηγούμενη ερώτηση):

Ερώτηση 3 (25β) Δίνεται η διαφορική εξίσωση

\[-u_{xx} + 3xu_x + (x+5)u = 4x\]

στο διάστημα $D = [3, 4]$ με συνοριακές συνθήκες $u(3) = 0.0000$, $u(4) = 1.0000$ Διακριτοποιούμε με κεντρισμένες πεπερασμένες διαφορές και πλέγμα 37 κόμβων στο $D$, όπου $x_0 = 3$, $x_{36} = 4$ και οι υπόλοιποι 35 κόμβοι είναι εσωτερικοί στο $D$. Όλοι οι κόμβοι ισαπέχουν. Το διάνυσμα των αγνώστων συμβολίζουμε με $U = [U_1, U_2, \dots, U_{35}]^T$. Να γράψετε την υπ' αριθμ. 35 εξίσωση του γραμμικού συστήματος που προκύπτει από τη διακριτοποίηση. Προσοχή: Για να είναι αποδεκτοί, οι συντελεστές πρέπει να γραφτούν σε δεκαδική μορφή, δηλ. πρόσημο, ακέραιο μέρος και 4 δεκαδικά ψηφία δεξιά της υποδιαστολής. Δεν πρέπει να χρειάζονται επιπλέον πράξεις για τον υπολογισμό τους.

2024___4_.jpg¶

Ερώτηση 4 (20β) Δίνονται το διάνυσμα και τα μητρώα: $\ell = \begin{pmatrix} -2 \\ 2 \end{pmatrix}$, $U = \begin{pmatrix} -2 & -1 \\ 1 & 2 \end{pmatrix}$, $V = \begin{pmatrix} 4 & 3 \\ 2 & 1 \\ -5 & -6 \end{pmatrix}$, $W = \begin{pmatrix} 0 & 2 \\ 0 & 2 \end{pmatrix}$. Αυτά τα χρησιμοποιούμε για να ορίσουμε την αναπαράσταση Kruskal

\[T = [\![\ell; U, V, W]\!] = \sum_i \lambda_i u_i \circ v_i \circ w_i\]

όπου ως συνήθως, $\lambda_i, u_i, v_i, w_i$ είναι στοιχεία και στήλες των $\ell, U, V, W$.

Να υπολογίσετε το $T_{2,:,:}$ και να γράψετε το αποτέλεσμα.

\[T_{2,:,:} = \begin{pmatrix} \end{pmatrix}\]

Δίνεται επίσης το διάνυσμα $B = \begin{pmatrix} -1 \\ 0 \\ -1 \end{pmatrix}$. Από τα δοθέντα δεδομένα, υπολογίστε το τροπικό γινόμενο $P = T \bar{\times}_2 B$.

Υπόδειξη: Πρόκειται για γινόμενο τανυστή με διάνυσμα (όπως π.χ. στο ttv). Το αποτέλεσμα είναι τανυστής βαθμού 2.

\[P = \begin{pmatrix} \end{pmatrix}\]

2024___5.1-2.jpg¶

Ερώτηση 5 (25β) Κάτω αριστερά στο σχήμα δίνεται το μητρώο $A \in \mathbb{R}^{6 \times 6}$. Στο υπόλοιπο σχήμα, δίνονται οι αριθμημένες κορυφές του γραφήματος του μητρώου.

[Σχήμα: Πλαίσιο που περιέχει κάτω αριστερά το μητρώο A διάστασης 6x6: 85 0 12 0 18 24 0 31 0 0 0 0 12 0 43 0 0 0 0 0 0 31 0 0 18 0 0 0 49 0 24 0 0 0 0 55 και 6 αριθμημένες κορυφές 1 έως 6]

Συμπληρώστε το παραπάνω γράφημα με (μη κατευθυνόμενες) ακμές, παραλείποντας τους αυτοβρόχους, ώστε το σχήμα να περιέχει το γράφημα του μητρώου (πλην αυτοβρόχων).
Συμπληρώστε τον πίνακα με τα στοιχεία της αναπαράστασης CSR του Α. (PTR είναι ο πίνακας των pointers της αραιής αναπαράστασης). Προσοχή: Κάθε υποπίνακας δίνεται με ακριβώς 20 θέσεις (στήλες). Εσείς ξεκινάτε από την πρώτη στήλη, και αφήνετε κενές όσες από τις τελευταίες θέσεις δεν χρειαστούν. Απάντηση υποερωτήματος 2:

										VAL

										IDX

										PTR

2024___5.3.jpg¶

Έστω $R = \text{chol}(A)$. Χωρίς να υπολογίσετε το $R$, βρείτε σε ποιές θέσεις αυτό θα περιέχει μη μηδενικές τιμές αποκλειστικά με πράξεις επί του γραφήματος (π.χ. προσθήκη ακμών με διαφορετική διαγράμμιση). Με βάση αυτό, ξαναγράψτε και συμπληρώστε τον πίνακα παρακάτω με την αραιή αναπαράσταση του $A$ συμπεριλαμβάνοντας στο VAL τις θέσεις που θα χρειαστούν για να αποθηκευτεί το fill-in (γέμισμα), δηλ. τα νέα μη μηδενικά στοιχεία που θα περιλαμβάνει το μητρώο $R^\top + R$ (μπορεί να μην δημιουργείται και κανένα). Αρχικοποιείστε τις θέσεις αυτές με 0. Τέλος, συμπληρώστε και τις αντίστοιχες τιμές των IDX, PTR.

Απάντηση υποερωτήματος 3:

										VAL

										IDX

										PTR

IMG_0171.png¶

Ερώτηση 2 (10β)

Δίνεται το σύστημα συνήθων διαφορικών εξισώσεων $\frac{d}{dt}u(t) = Au(t)$, $u(0) = g$, όπου $A$ είναι αντιστρέψιμο με αρνητικές ιδιοτιμές και το $g$ γνωστό διάνυσμα. Θέλουμε να προσεγγίσουμε το $u(h)$ για μικρό $h$. Στις ερωτήσεις παρακάτω υπενθυμίζουμε ότι είναι απαραίτητη η αιτιολόγηση.

Με βάση το γνωστό τύπο για την αναλυτική λύση του παραπάνω προβλήματος, να μαυρίσετε το κουτάκι της μοναδικής από τις παρακάτω εκφράσεις που είναι προσέγγιση του $u(h)$. Ως συνήθως, $I$ είναι το ταυτοτικό μητρώο.
[ ] $(I + Ah/2)^{-1}(I + Ah/2)^{-1} g$
[ ] $(I - Ah/2)^{-1}(I - Ah/2)^{-1} g$
[ ] $(I - Ah/2 + A^2h^2/4)^{-1} g$
[ ] $(I + Ah + A^2h^2/2)^{-1} g$

[Σχήμα: τέσσερα πλαίσια επιλογής (□) σε δύο στήλες δίπλα στις παραπάνω εκφράσεις· στην αριστερή στήλη οι δύο πρώτες επιλογές, στη δεξιά οι δύο τελευταίες.]

Έστω ότι $A$ είναι τριδιαγώνιο. Θεωρούμε ότι όλες οι πράξεις με το $A$ είναι επιτρεπτές (π.χ. οποιοδήποτε σύστημα πρέπει να λυθεί είναι επιλύσιμο.) Αν υπολογίζατε με τον τύπο που επιλέξατε παραπάνω την προσέγγιση του $u(h)$ να βρείτε και να αιτιολογήσετε ποιός είναι ασυμπτωτικά ο κυρίαρχος όρος για το πλήθος των αριθμητικών πράξεων για τον εν λόγω υπολογισμό αν αυτός γίνει με το βέλτιστο δυνατό άμεσο (μη επαναληπτικό) τρόπο (π.χ. αξιοποιώντας τη δομή του μητρώου, παραγοντοποιήσεις, κ.λπ.) Για παράδειγμα, αν ο κυρίαρχος όρος είναι $\frac{3}{2}n^4$, μπορείτε να γράψετε $O(n^4)$, κ.ο.κ.

[Λείπει από τη φωτογραφία: η αρχή της επικεφαλίδας· ορατό: «ότηση 3 (25β)»]

Ερώτηση 3 (25β)

Δίνονται τα παρακάτω:

\[u = \begin{pmatrix}-1\\1\end{pmatrix}, \quad v = \begin{pmatrix}-3\\4\\5\end{pmatrix}, \quad w = \begin{pmatrix}1\\2\\3\end{pmatrix}, \quad B = \begin{pmatrix}2 & 1\\-1 & 1\end{pmatrix}\]

ΚΙΝΗΤΑ ΚΛΕΙΣΤΑ. ΑΝΤΙΓΡΑΦΗ, ΔΙΑΚΙΝΗΣΗ, ΣΥΝΕΡΓΑΣΙΑ ΕΠΙΦΕΡΟΥΝ ΜΗΔΕΝΙΣΜΟ/ΑΝΑΦΟΡΑ.

Σημείωση: η αρχή της επικεφαλίδας της Ερώτησης 3 είναι κομμένη στο άκρο της φωτογραφίας. Η φωτογραφία είναι τραβηγμένη υπό γωνία και οι τύποι των επιλογών της Ερώτησης 1 είναι μικρού μεγέθους· η μεταγραφή τους βασίστηκε σε μεγέθυνση.

IMG_0173.png¶

[κομμένο κείμενο στο πάνω άκρο της σελίδας: «...με μηδενικά.»]

[Λείπει από τη φωτογραφία: το τυπωμένο πλαίσιο του αλγορίθμου FOM· η φωτογραφία δείχνει μόνο χειρόγραφο αντίγραφο του αλγορίθμου, το οποίο δεν μεταγράφεται]

Να γράψετε ως συνάρτηση τον αντίστοιχο κώδικα MATLAB στο δεξιό πλαίσιο. Προσοχή: Στόχος είναι η αποτελεσματική υλοποίηση, επομένως μπορείτε να χρησιμοποιήσετε όποιες συναρτήσεις της MATLAB θεωρείτε καλύτερες για την επίτευξη του στόχου, π.χ. norm για τον υπολογισμό της νόρμας, κ.λπ.
Να εφαρμόσετε $m = 1$ επανάληψη της FOM και να υπολογίσετε το $x_1$. Σε περίπτωση αστοχίας, να εξηγήσετε τι συμβαίνει.
Με βάση τα προηγούμενα αποτελέσματα, να συμπληρώσετε τις τιμές παρακάτω για το πρόβλημα ελαχίστων τετραγώνων που πρέπει να λυθεί έτσι ώστε $x_1 = x_0 + V_m y$ να είναι η αντίστοιχη προσέγγιση που επιστρέφει μόνον ένα βήμα της GMRES(1).

ΑΠΑΝΤΗΣΗ:

[Σχήμα: τύπος ελαχίστων τετραγώνων με κενά διανυσμάτων. Ο δείκτης του min είναι δυσανάγνωστος. Στο πρώτο διάνυσμα φαίνεται μόνο το 0 στη δεύτερη θέση. Τα υπόλοιπα κενά και η νόρμα $\|\cdot\|_2$ με το $y$ είναι ορατά ή δυσανάγνωστα όπως φαίνονται στη φωτογραφία.]

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

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

2025-01-27_15.39.53.png¶

Σημείωση: η φωτογραφία είναι διπλότυπο της Ερώτησης 1 της σελίδας «2024___1-3.jpg»· τα υποερωτήματα ταυτίζονται με τη μεταγραφή εκεί και δεν επαναλαμβάνονται.

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφίες λύσεων φοιτητών που μοιράστηκαν στο Discord (Ιούνιος 2024)

Προσοχή

Όλες οι λύσεις είναι φοιτητικές (Discord)· καμία δεν προέρχεται από επίσημο κλειδί του διδάσκοντα. Η Screenshot_2024-06-18_at_9.46.08 είναι μερική: ο πίνακας COLPTR δεν συμπληρώνεται πλήρως και φοιτητής αμφισβητεί την τελευταία τιμή του COLPTR (18 ή 19)· η απάντηση δεν επιβεβαιώνεται. Η Screenshot_2024-06-18_at_9.15.12 έχει σβησμένο με blanco τμήμα της εκφώνησης· η μεταγραφή σημειώνει το δυσανάγνωστο σημείο. Το S = T⁻¹ που δίνεται ελέγχθηκε: η πρώτη γραμμή (1, −2, 1, 0) συμφωνεί με τις δοθείσες τιμές e₁ᵀT⁻¹e₂ = −2, e₁ᵀT⁻¹e₃ = 1, e₁ᵀT⁻¹e₄ = 0. Η tempFileForShare_20240612 δίνει μόνο σύντομη σύνοψη για το Arnoldi (H τριδιαγώνιο)· η αιτιολόγηση της θέσης με μηδενικό στοιχείο δεν είναι πλήρης. Η άσκηση με τον τανυστή A (διαστάσεων 1×2×3) και το μητρώο B της φωτογραφίας 129.png δεν εμφανίζεται στη μεταγραφή της εξέτασης Ιουνίου 2024· η αντιστοίχισή της με θέμα της εξέτασης δεν έχει επαληθευθεί. Η φωτογραφία bf11d90f90770a4a.JPG έχει το ίδιο κείμενο και δεν μεταγράφεται ξανά. Στη λύση της 129.png, η δεύτερη γραμμή του P_(3) «(−5, 2)» δεν συμφωνεί με τον άμεσο υπολογισμό P(1,:,2) = Σ_l A(1,:,l)·B(2,l) = (−5, −6)· η γραμμή «P_(3) = A_(3)» δεν είναι συνεπής με τις διαστάσεις (A_(3) είναι 3×2). Το P(1,:,1) = (−11, −8) επαληθεύεται.

Λύσεις — Επιστημονικός Υπολογισμός — Ιούνιος 2024¶

Οι λύσεις είναι φοιτητικές και σε μορφή αποσπασμάτων (στιγμιότυπα οθόνης και φωτογραφίες). Δεν καλύπτουν όλα τα ερωτήματα της εξέτασης.

2024-06-04_174237.png¶

ΑΠΑΝΤΗΣΗ: Το κυρίαρχο κόστος οφείλεται στην επίλυση του $(A + uv^\top)x = u$ που υλοποιείται από την ανάποδη κάθετο στη MATLAB. Δεδομένου ότι το μητρώο $A + uv^\top$ είναι πυκνό, το κόστος αντιστοιχεί στη χρήση της LU που ως γνωστόν είναι $2/3 n^3$ και άρα $\alpha = 2/3$.

Απλοποιήστε τα παραπάνω λαμβάνοντας υπόψη τα δεδομένα και τη δομή τους ώστε να επιτευχθεί μαθηματικά ισοδύναμος υπολογισμός του $s$ με όσο μπορείτε μικρότερο $\Omega$. Συμπληρώστε στο πλαίσιο τις αντίστοιχες εντολές MATLAB (η τελευταία εντολή είναι η ανάθεση στο $s$). Όπως πριν, να υπολογίσετε και να αναφέρετε το συντελεστή του νέου μεγιστοβάθμιου όρου στο νέο $\Omega$.

ΣΥΝΟΨΗ ΑΠΑΝΤΗΣΗΣ: Είναι $\gamma = 3$. Βάσει του τύπου Sherman-Morrison,

\[s = v^\top (A^{-1} + A^{-1}u(1 - v^\top A^{-1}u)^{-1}v^\top A^{-1})u\]

και με λίγη περαιτέρω επεξεργασία (που πρέπει να πραγματοποιήσετε και να εξηγήσετε) προκύπτει ότι

το κυρίαρχο κόστος είναι $\Omega = 3n$,

% Οι εντολές είναι
t = v'*(u./diag(A))
s = t+t^2/(1-t)

129.png¶

Ερώτηση: Δίνεται ο 3-mode τανυστής $A$ διαστάσεων $1 \times 2 \times 3$ με στοιχεία

\[A(:,:,1) = \begin{pmatrix} 0 & -4 \end{pmatrix}$$ $$A(:,:,2) = \begin{pmatrix} 2 & 2 \end{pmatrix}$$ $$A(:,:,3) = \begin{pmatrix} -7 & -4 \end{pmatrix}\]

Δίνεται και το μητρώο

\[B = \begin{pmatrix} 0 & -2 & 1 \\ 1 & 1 & 1 \end{pmatrix}\]

Να συμπληρώσετε παρακάτω τις διαστάσεις του τανυστή $P$ που προκύπτει απο το τροπικό γινόμενο, $P = A \times_3 B$. ΑΠΑΝΤΗΣΗ: Το μητρώο $P_{(3)} = A_{(3)}$ θα είναι $2 \times 3 \times 3 \times (1 \times 2)$ και επομένως οι διαστάσεις του $P$ θα είναι $1 \times 2 \times 2$
Να υπολογίσετε το $P(1,:,1)$ και να γράψετε ακριβώς το αποτέλεσμα ανάλογα με τη μορφή του (αν είναι διάνυσμα, προσοχή να έχει το σωστό προσανατολισμό ως στήλη ή γραμμή). ΑΠΑΝΤΗΣΗ: Θα ισχύει ότι $P_{(3)} = A_{(3)} = \begin{pmatrix} -11 & -8 \\ -5 & 2 \end{pmatrix}$ επομένως $P(1,:,1) = \begin{pmatrix} -11.00 \\ -8.00 \end{pmatrix}$

tempFileForShare_20240612-125532.jpg¶

Δίνεται το αντιστρέψιμο και συμμετρικό θετικά ορισμένο τετραγωνικό μητρώο $A$ και μας ενδιαφέρει η επίλυση του γραμμικού συστήματος $Ax = b$. Χρησιμοποιούμε Arnoldi και κατασκευάζουμε βάση ορθοκανονικών διανυσμάτων $\{v_1, v_2, v_3\}$, όπου $v_1 = b/\|b\|_2$, για τον υπόχωρο Krylov $K_3(A, b)$ και θέτουμε $V = [v_1, v_2, v_3]$. Σε ποια θέση (ή ποιες θέσεις) θα έχει τιμή 0 το μητρώο $H = V^\top AV$ και γιατί;

ΣΥΝΟΨΗ ΑΠΑΝΤΗΣΗΣ: Εδώ αξιοποιούμε το ότι το μητρώο $H$ θα είναι άνω Hessenberg (γιατι;) αλλά λόγω συμμετρίας του $A$ και συμμετρικό, άρα το $H$ θα είναι τριδιαγώνιο.

Screenshot_2024-06-18_at_9.15.12_PM.png¶

ΕΠΙΛΕΓΜΕΝΕΣ ΑΠΑΝΤΗΣΕΙΣ “ΕΠΙ [κομμένο]

Ερώτηση 1. Δίνεται το μητρώο $T = [1,2,3,4;0,1,2,3;0,0,1,2;0,0,0,1]$. Γνωρίζουμε επίσης ότι

\[e_1^\top T^{-1} e_2 = -2, \quad e_1^\top T^{-1} e_3 = 1, \quad e_1^\top T^{-1} e_4 = 0.\]

Πραγματοποιώντας τους ελάχιστους δυνατούς υπολογισμούς και με βάση όσα γνωρίζετε από τη θεωρία, να υπολογίστε τις τιμές του $S = T^{-1}$ και να τις συμπληρώσετε παρακάτω. Υπόδειξη: Μην επιχειρήσετε (δεν χρειάζεται και είναι δαπανηρό) να προβείτε στην αντιστροφή του $T$ μέσω $LU$ ή Gauss.

ΣΥΝΟΨΗ ΑΠΑΝΤΗΣΗΣ

Το $T$ είναι άνω τριγωνικό Toeplitz, επομένως βάσει της θεωρίας, το ίδιο θα ισχύει και για το $S = T^{-1}$. Από τις δοθείσες σχέσεις, τα στοιχεία της πρώτης γραμμής του $S$ εκτός από το στοιχείο της κυρίας διαγωνίου είναι γνωστά. Άρα αρκεί να υπολογίσουμε το $e_1^\top T^{-1} e_1$, [δυσανάγνωστο] Αυτό είναι ιδιαίτερα εύκολο λόγω της δομής του $T$ και του δεξιού μέλους.

Με λίγη σκέψη προκύπτει ότι

\[S = [1, -2, 1, 0; 0, 1, -2, 1; 0, 0, 1, -2; 0, 0, 0, 1]\]

Screenshot_2024-06-18_at_9.46.08_PM.png¶

Έστω $R=\mathrm{chol}(A)$. Χωρίς να υπολογίσετε το $R$, βρείτε σε ποιες θέσεις αυτό θα περιέχει μη μηδενικές τιμές αποκλειστικά με πράξεις επί του γραφήματος (π.χ. προσθήκη ακμών με διαφορετική διαγραμμίση). Με βάση αυτό, ξαναγράψτε και συμπληρώστε τον πίνακα παρακάτω με την αραιή αναπαράσταση του $A$ συμπεριλαμβάνοντας στο VAL τις θέσεις που θα χρειαστούν για να αποθηκευτεί το fill-in (γέμισμα), δηλ. τα νέα μη μηδενικά στοιχεία που θα περιλαμβάνει το μητρώο $R^\top + R$ (μπορεί να μην δημιουργείται και κανένα). Αρχικοποιήστε τις θέσεις αυτές με 0. Τέλος, συμπληρώστε και τις αντίστοιχες τιμές των IDX, PTR.

Το μητρώο είναι $6 \times 6$, επομένως σύμφωνα με όσα έχουμε δείξει στις διαλέξεις, για κάθε βήμα $i = 1, \ldots, 5$ της απαλοιφής, σημειώνουμε τις κορυφές $i+1, \ldots, n$ με τις οποίες συνδέεται η $i$ με ακμή $(i,j)$, διαγράφουμε αυτές τις ακμές και εισάγουμε νέες ακμές ώστε οι κορυφές που γειτονεύουν με την $i$ να δημιουργούν κλίκα. Στο τέλος της διαδικασίας, οι νέες ακμές $(i,j)$ θα αντιστοιχούν στις θέσεις του fill-in. Σημειώνουμε τις θέσεις αυτές και γράφουμε την νέα αραιή αναπαράσταση, ενθέτοντας μηδενικά στις θέσεις του VAL και προσαρμόζοντας τις τιμές των πινάκων IDX και PTR.

VAL	34	5	5	3	5	26	0	0	5	0	26	0	21	3	0	0	24	21
ROWIDX	1	2	3	5	1	2	3	5	1	2	3	5	4	1	2	3	5	6
COLPTR	1	5	9	13	14	17	18

[Αριστερό περιθώριο: αποκομμένα τμήματα άλλων γραμμών κειμένου, δεν μεταγράφονται.]

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή