poster
2025-02-10, 08:57
LUTool provides an interactive animation of Gaussian elimination, the most important algorithm in technical computing.
Contents
LU Matrix Factorization (https://www.labfans.com/bbs/#9a082e23-5f77-439b-87dc-27e094abd2ea)
LUTool (https://www.labfans.com/bbs/#db10948f-e8f6-4220-9707-a33f965c2272)
Magic Squares (https://www.labfans.com/bbs/#6b4793de-6686-4da5-91ce-363fc58c068b)
Positive Definite Matrices (https://www.labfans.com/bbs/#b5f1a600-244e-4bff-823c-210673ec5273)
Redheffer Matrices (https://www.labfans.com/bbs/#84f5b49b-4243-477d-96d3-87c8d72c829d)
Singular Matrices (https://www.labfans.com/bbs/#5b2600ac-9536-457c-a935-7e35339edb57)
Software (https://www.labfans.com/bbs/#ab040aa1-def2-4b72-b9a9-945da1a77b19)
LU Matrix Factorization
The triangular factorization of a square, n-by-n matrix A is
A(p,q) = L*Uwhere L is a lower triangular matrix with ones on the diagonal, U is an upper triangular matrix, and p and q are indices of row and column permutations.
There are three kinds of pivoting.
* none. No interchanges.* partial. Choose the largest element in the current pivot column.* complete. Choose the largest element in the entire unreduced matrix.In general, pivoting permutations are necessary for numerical stability by avoiding divisions by small pivots. However, some test matrices can be successfully factored without pivoting.
LUTool
LUTool displays the lower portion of L and the row indices p in blue and the upper portion of U and the column indices q in lavender. The product of the pivot values on the diagonal of U is the determinant of A.
A popup menu lists the available test matrix families from gallery and from the MATLAB path. info and help buttons display information about the selected family and about LUTool itself.
https://blogs.mathworks.com/cleve/files/magic_3_static.gif
Magic Squares
Here are the three pivoting options with the 5-by-5 magic square.
complete
https://blogs.mathworks.com/cleve/files/magic_5_complete.gif
partial
https://blogs.mathworks.com/cleve/files/magic_5_partial.gif
none
https://blogs.mathworks.com/cleve/files/magic_5_none.gif
Positive Definite Matrices
Pascal matrices are positive definite and do not require pivoting. The same triangular factorization is computed by chol.
https://blogs.mathworks.com/cleve/files/pascal_6_none.gif
Redheffer Matrices
Last fall, I made a series of blog posts (https://blogs.mathworks.com/cleve/2024/09/23/redheffer-mertens-and-one-million-dollars/) about Redheffer matrices and the Riemann hypothesis. Since the first column of a Redheffer matrix is all ones, the resulting lower triangular factor is nearly full.
https://blogs.mathworks.com/cleve/files/redheff_7_partial.gif
Pat Quillen suggested interchanging the first and last columns, so there would be much less fill-in.
https://blogs.mathworks.com/cleve/files/redheff_3_7_partial.gif
Singular Matrices
It is widely believed that only nonsingular matrices have triangular factorizations. However, with proper pivoting, singular matrices also have LU factorizations. (The consequences of singularity or poor conditioning are realized when U is subsequently used to solve a linear system.)
For example, restart the random number generator with
rng(1)Then
n = 6 gallery('rando',n,0)produces a singular matrix and
[A,p,q,L,U] = LUTool('rando',n,'partial',0.02)encounters two zero pivots. Nevertheless, the output satisfies
A(p,q) = L*Uhttps://blogs.mathworks.com/cleve/files/rando_6_partial.gif
For my final example, the rank of the 8-by-8 magic square is only 3. LUTool with partial pivoting encounters five negligible pivots. The first three columns of L and the first three rows of U are all that is required to reconstruct the original magic square.
https://blogs.mathworks.com/cleve/files/magic_8_partial.gif
Software
A self-extracting archive of LUTool is available from this link (https://blogs.mathworks.com/cleve/files/LUTool_mzip.m)
Get the MATLAB code (requires JavaScript) (javascript:grabCode_39dca6aaf7274169876a8296cc5c2505())
Published with MATLAB® R2024b
More... (https://blogs.mathworks.com/cleve/2025/02/08/lutool-animation-of-gaussian-elimination/?s_tid=feedtopost)
Contents
LU Matrix Factorization (https://www.labfans.com/bbs/#9a082e23-5f77-439b-87dc-27e094abd2ea)
LUTool (https://www.labfans.com/bbs/#db10948f-e8f6-4220-9707-a33f965c2272)
Magic Squares (https://www.labfans.com/bbs/#6b4793de-6686-4da5-91ce-363fc58c068b)
Positive Definite Matrices (https://www.labfans.com/bbs/#b5f1a600-244e-4bff-823c-210673ec5273)
Redheffer Matrices (https://www.labfans.com/bbs/#84f5b49b-4243-477d-96d3-87c8d72c829d)
Singular Matrices (https://www.labfans.com/bbs/#5b2600ac-9536-457c-a935-7e35339edb57)
Software (https://www.labfans.com/bbs/#ab040aa1-def2-4b72-b9a9-945da1a77b19)
LU Matrix Factorization
The triangular factorization of a square, n-by-n matrix A is
A(p,q) = L*Uwhere L is a lower triangular matrix with ones on the diagonal, U is an upper triangular matrix, and p and q are indices of row and column permutations.
There are three kinds of pivoting.
* none. No interchanges.* partial. Choose the largest element in the current pivot column.* complete. Choose the largest element in the entire unreduced matrix.In general, pivoting permutations are necessary for numerical stability by avoiding divisions by small pivots. However, some test matrices can be successfully factored without pivoting.
LUTool
LUTool displays the lower portion of L and the row indices p in blue and the upper portion of U and the column indices q in lavender. The product of the pivot values on the diagonal of U is the determinant of A.
A popup menu lists the available test matrix families from gallery and from the MATLAB path. info and help buttons display information about the selected family and about LUTool itself.
https://blogs.mathworks.com/cleve/files/magic_3_static.gif
Magic Squares
Here are the three pivoting options with the 5-by-5 magic square.
complete
https://blogs.mathworks.com/cleve/files/magic_5_complete.gif
partial
https://blogs.mathworks.com/cleve/files/magic_5_partial.gif
none
https://blogs.mathworks.com/cleve/files/magic_5_none.gif
Positive Definite Matrices
Pascal matrices are positive definite and do not require pivoting. The same triangular factorization is computed by chol.
https://blogs.mathworks.com/cleve/files/pascal_6_none.gif
Redheffer Matrices
Last fall, I made a series of blog posts (https://blogs.mathworks.com/cleve/2024/09/23/redheffer-mertens-and-one-million-dollars/) about Redheffer matrices and the Riemann hypothesis. Since the first column of a Redheffer matrix is all ones, the resulting lower triangular factor is nearly full.
https://blogs.mathworks.com/cleve/files/redheff_7_partial.gif
Pat Quillen suggested interchanging the first and last columns, so there would be much less fill-in.
https://blogs.mathworks.com/cleve/files/redheff_3_7_partial.gif
Singular Matrices
It is widely believed that only nonsingular matrices have triangular factorizations. However, with proper pivoting, singular matrices also have LU factorizations. (The consequences of singularity or poor conditioning are realized when U is subsequently used to solve a linear system.)
For example, restart the random number generator with
rng(1)Then
n = 6 gallery('rando',n,0)produces a singular matrix and
[A,p,q,L,U] = LUTool('rando',n,'partial',0.02)encounters two zero pivots. Nevertheless, the output satisfies
A(p,q) = L*Uhttps://blogs.mathworks.com/cleve/files/rando_6_partial.gif
For my final example, the rank of the 8-by-8 magic square is only 3. LUTool with partial pivoting encounters five negligible pivots. The first three columns of L and the first three rows of U are all that is required to reconstruct the original magic square.
https://blogs.mathworks.com/cleve/files/magic_8_partial.gif
Software
A self-extracting archive of LUTool is available from this link (https://blogs.mathworks.com/cleve/files/LUTool_mzip.m)
Get the MATLAB code (requires JavaScript) (javascript:grabCode_39dca6aaf7274169876a8296cc5c2505())
Published with MATLAB® R2024b
More... (https://blogs.mathworks.com/cleve/2025/02/08/lutool-animation-of-gaussian-elimination/?s_tid=feedtopost)