LUTool, Animation of Gaussian Elimination - Cleve Moler on Mathematics and Computing
 

LUTool provides an interactive animation of Gaussian elimination, the most important algorithm in technical computing.

[B]Contents[/B]
[LIST][*][URL="https://www.labfans.com/bbs/#9a082e23-5f77-439b-87dc-27e094abd2ea"]LU Matrix Factorization[/URL][*][URL="https://www.labfans.com/bbs/#db10948f-e8f6-4220-9707-a33f965c2272"]LUTool[/URL][*][URL="https://www.labfans.com/bbs/#6b4793de-6686-4da5-91ce-363fc58c068b"]Magic Squares[/URL][*][URL="https://www.labfans.com/bbs/#b5f1a600-244e-4bff-823c-210673ec5273"]Positive Definite Matrices[/URL][*][URL="https://www.labfans.com/bbs/#84f5b49b-4243-477d-96d3-87c8d72c829d"]Redheffer Matrices[/URL][*][URL="https://www.labfans.com/bbs/#5b2600ac-9536-457c-a935-7e35339edb57"]Singular Matrices[/URL][*][URL="https://www.labfans.com/bbs/#ab040aa1-def2-4b72-b9a9-945da1a77b19"]Software[/URL][/LIST][B]LU Matrix Factorization[/B]

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.

[B]LUTool[/B]

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.

[IMG]https://blogs.mathworks.com/cleve/files/magic_3_static.gif[/IMG]

[B]Magic Squares[/B]

Here are the three pivoting options with the 5-by-5 magic square.

[B]complete[/B]

[IMG]https://blogs.mathworks.com/cleve/files/magic_5_complete.gif[/IMG]

[B]partial[/B]

[IMG]https://blogs.mathworks.com/cleve/files/magic_5_partial.gif[/IMG]

[B]none[/B]

[IMG]https://blogs.mathworks.com/cleve/files/magic_5_none.gif[/IMG]

[B]Positive Definite Matrices[/B]

Pascal matrices are positive definite and do not require pivoting. The same triangular factorization is computed by chol.

[IMG]https://blogs.mathworks.com/cleve/files/pascal_6_none.gif[/IMG]

[B]Redheffer Matrices[/B]

Last fall, I made [URL="https://blogs.mathworks.com/cleve/2024/09/23/redheffer-mertens-and-one-million-dollars/"]a series of blog posts[/URL] 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.

[IMG]https://blogs.mathworks.com/cleve/files/redheff_7_partial.gif[/IMG]

Pat Quillen suggested interchanging the first and last columns, so there would be much less fill-in.

[IMG]https://blogs.mathworks.com/cleve/files/redheff_3_7_partial.gif[/IMG]

[B]Singular Matrices[/B]

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*U[IMG]https://blogs.mathworks.com/cleve/files/rando_6_partial.gif[/IMG]

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.

[IMG]https://blogs.mathworks.com/cleve/files/magic_8_partial.gif[/IMG]

[B]Software[/B]

A self-extracting archive of LUTool is available from [URL="https://blogs.mathworks.com/cleve/files/LUTool_mzip.m"]this link[/URL]

[RIGHT][COLOR=gray][I]
[URL="javascript:grabCode_39dca6aaf7274169876a8296cc5c2505()"][I]Get the MATLAB code (requires JavaScript)[/I][/URL]

Published with MATLAB® R2024b
[/I][/COLOR][/RIGHT]




[url=https://blogs.mathworks.com/cleve/2025/02/08/lutool-animation-of-gaussian-elimination/?s_tid=feedtopost]More...[/url]