{"id":12359,"date":"2025-02-08T21:45:38","date_gmt":"2025-02-09T02:45:38","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=12359"},"modified":"2025-02-08T21:45:38","modified_gmt":"2025-02-09T02:45:38","slug":"lutool-animation-of-gaussian-elimination","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2025\/02\/08\/lutool-animation-of-gaussian-elimination\/","title":{"rendered":"LUTool, Animation of Gaussian Elimination"},"content":{"rendered":"<div class=\"content\"><!--introduction-->\r\n<p>\r\n<tt>LUTool<\/tt> provides an interactive animation of Gaussian elimination, the most important algorithm in technical computing.<\/p>\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n<li>\r\n<a href=\"#9a082e23-5f77-439b-87dc-27e094abd2ea\">LU Matrix Factorization<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#db10948f-e8f6-4220-9707-a33f965c2272\"><tt>LUTool<\/tt><\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#6b4793de-6686-4da5-91ce-363fc58c068b\">Magic Squares<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#b5f1a600-244e-4bff-823c-210673ec5273\">Positive Definite Matrices<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#84f5b49b-4243-477d-96d3-87c8d72c829d\">Redheffer Matrices<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#5b2600ac-9536-457c-a935-7e35339edb57\">Singular Matrices<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#ab040aa1-def2-4b72-b9a9-945da1a77b19\">Software<\/a>\r\n<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>LU Matrix Factorization<a name=\"9a082e23-5f77-439b-87dc-27e094abd2ea\"><\/a>\r\n<\/h4>\r\n<p>The triangular factorization of a square, n-by-n matrix <tt>A<\/tt> is<\/p>\r\n<pre>  A(p,q) = L*U<\/pre>\r\n<p>where <tt>L<\/tt> is a lower triangular matrix with ones on the diagonal, <tt>U<\/tt> is an upper triangular matrix, and p and q are indices of row and column permutations.<\/p>\r\n<p>There are three kinds of pivoting.<\/p>\r\n<pre>* none. No interchanges.\r\n* partial. Choose the largest element in the current pivot column.\r\n* complete. Choose the largest element in the entire unreduced matrix.<\/pre>\r\n<p>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.<\/p>\r\n<h4>\r\n<tt>LUTool<\/tt><a name=\"db10948f-e8f6-4220-9707-a33f965c2272\"><\/a>\r\n<\/h4>\r\n<p>\r\n<tt>LUTool<\/tt> displays the lower portion of <tt>L<\/tt> and the row indices <tt>p<\/tt> in blue and the upper portion of <tt>U<\/tt> and the column indices <tt>q<\/tt> in lavender. The product of the pivot values on the diagonal of <tt>U<\/tt> is the determinant of <tt>A<\/tt>.<\/p>\r\n<p>A popup menu lists the available test matrix families from <tt>gallery<\/tt> and from the MATLAB path. <tt>info<\/tt> and <tt>help<\/tt> buttons display information about the selected family and about <tt>LUTool<\/tt> itself.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/magic_3_static.gif\" alt=\"\"> <\/p>\r\n<h4>Magic Squares<a name=\"6b4793de-6686-4da5-91ce-363fc58c068b\"><\/a>\r\n<\/h4>\r\n<p>Here are the three pivoting options with the 5-by-5 magic square.<\/p>\r\n<p>\r\n<b>complete<\/b>\r\n<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/magic_5_complete.gif\" alt=\"\"> <\/p>\r\n<p>\r\n<b>partial<\/b>\r\n<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/magic_5_partial.gif\" alt=\"\"> <\/p>\r\n<p>\r\n<b>none<\/b>\r\n<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/magic_5_none.gif\" alt=\"\"> <\/p>\r\n<h4>Positive Definite Matrices<a name=\"b5f1a600-244e-4bff-823c-210673ec5273\"><\/a>\r\n<\/h4>\r\n<p>Pascal matrices are positive definite and do not require pivoting. The same triangular factorization is computed by <tt>chol<\/tt>.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/pascal_6_none.gif\" alt=\"\"> <\/p>\r\n<h4>Redheffer Matrices<a name=\"84f5b49b-4243-477d-96d3-87c8d72c829d\"><\/a>\r\n<\/h4>\r\n<p>Last fall, I made <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">a series of blog posts<\/a> 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.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/redheff_7_partial.gif\" alt=\"\"> <\/p>\r\n<p>Pat Quillen suggested interchanging the first and last columns, so there would be much less fill-in.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/redheff_3_7_partial.gif\" alt=\"\"> <\/p>\r\n<h4>Singular Matrices<a name=\"5b2600ac-9536-457c-a935-7e35339edb57\"><\/a>\r\n<\/h4>\r\n<p>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 <tt>U<\/tt> is subsequently used to solve a linear system.)<\/p>\r\n<p>For example, restart the random number generator with<\/p>\r\n<pre>  rng(1)<\/pre>\r\n<p>Then<\/p>\r\n<pre>  n = 6\r\n  gallery('rando',n,0)<\/pre>\r\n<p>produces a singular matrix and<\/p>\r\n<pre>  [A,p,q,L,U] = LUTool('rando',n,'partial',0.02)<\/pre>\r\n<p>encounters two zero pivots. Nevertheless, the output satisfies<\/p>\r\n<pre>  A(p,q) = L*U<\/pre>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/rando_6_partial.gif\" alt=\"\"> <\/p>\r\n<p>For my final example, the rank of the 8-by-8 magic square is only 3. <tt>LUTool<\/tt> with partial pivoting encounters five negligible pivots. The first three columns of <tt>L<\/tt> and the first three rows of <tt>U<\/tt> are all that is required to reconstruct the original magic square.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/magic_8_partial.gif\" alt=\"\"> <\/p>\r\n<h4>Software<a name=\"ab040aa1-def2-4b72-b9a9-945da1a77b19\"><\/a>\r\n<\/h4>\r\n<p>A self-extracting archive of <tt>LUTool<\/tt> is available from <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/LUTool_mzip.m\">this link<\/a>\r\n<\/p>\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_39dca6aaf7274169876a8296cc5c2505() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='39dca6aaf7274169876a8296cc5c2505 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 39dca6aaf7274169876a8296cc5c2505';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2025 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\">\r\n<br>\r\n<a href=\"javascript:grabCode_39dca6aaf7274169876a8296cc5c2505()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript>\r\n<\/span><\/a>\r\n<br>\r\n<br>\r\n      Published with MATLAB&reg; R2024b<br>\r\n<\/p>\r\n<\/div>\r\n<!--\r\n39dca6aaf7274169876a8296cc5c2505 ##### SOURCE BEGIN #####\r\n%% LUTool, Animation of Gaussian Elimination\r\n% |LUTool| provides an interactive animation of Gaussian elimination,\r\n% the most important algorithm in technical computing.\r\n\r\n%% LU Matrix Factorization\r\n% The triangular factorization of a square, n-by-n matrix |A| is\r\n%\r\n%    A(p,q) = L*U\r\n%\r\n% where |L| is a lower triangular matrix with ones on the diagonal,\r\n% |U| is an upper triangular matrix, and p and q are indices of\r\n% row and column permutations.\r\n%\r\n% There are three kinds of pivoting.\r\n%\r\n%  * none. No interchanges.\r\n%  * partial. Choose the largest element in the current pivot column.\r\n%  * complete. Choose the largest element in the entire unreduced matrix.\r\n%\r\n% In general, pivoting permutations are necessary for numerical stability\r\n% by avoiding divisions by small pivots.  However, some test matrices\r\n% can be successfully factored without pivoting.\r\n\r\n%% |LUTool|\r\n% |LUTool| displays the lower portion of |L| and the row indices |p|\r\n% in blue and the upper portion of |U| and the column indices |q|\r\n% in lavender.  The product of the pivot values on the diagonal of |U|\r\n% is the determinant of |A|.\r\n%\r\n% A popup menu lists the available test matrix families from |gallery|\r\n% and from the MATLAB path. |info| and |help| buttons display\r\n% information about the selected family and about |LUTool| itself.\r\n%\r\n% <<magic_3_static.gif>>\r\n%\r\n\r\n%% Magic Squares\r\n% Here are the three pivoting options with the 5-by-5 magic square.\r\n%\r\n% *complete*\r\n% \r\n% <<magic_5_complete.gif>>\r\n%\r\n% *partial*\r\n% \r\n% <<magic_5_partial.gif>>\r\n%\r\n% *none*\r\n% \r\n% <<magic_5_none.gif>>\r\n\r\n%% Positive Definite Matrices\r\n% Pascal matrices are positive definite and do not require pivoting. \r\n% The same triangular factorization is computed by |chol|.\r\n%\r\n% <<pascal_6_none.gif>>\r\n%\r\n\r\n%% Redheffer Matrices\r\n% Last fall, I made\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\r\n% a series of blog posts> about Redheffer matrices and the Riemann\r\n% hypothesis.  Since the first column of a Redheffer matrix is all ones,\r\n% the resulting lower triangular factor is nearly full.\r\n%\r\n% <<redheff_7_partial.gif>>\r\n%\r\n% Pat Quillen suggested interchanging the first and last columns, so\r\n% there would be much less fill-in.\r\n%\r\n% <<redheff_3_7_partial.gif>>\r\n%\r\n\r\n%% Singular Matrices\r\n% It is widely believed that only nonsingular matrices have triangular\r\n% factorizations.  However, with proper pivoting, singular matrices also\r\n% have LU factorizations.  (The consequences of singularity or poor\r\n% conditioning are realized when |U| is subsequently used to solve\r\n% a linear system.)\r\n%\r\n% For example, restart the random number generator with\r\n% \r\n%    rng(1)\r\n%\r\n% Then\r\n%\r\n%    n = 6\r\n%    gallery('rando',n,0)\r\n%\r\n% produces a singular matrix and\r\n%\r\n%    [A,p,q,L,U] = LUTool('rando',n,'partial',0.02)\r\n%\r\n% encounters two zero pivots.  Nevertheless, the output satisfies\r\n%\r\n%    A(p,q) = L*U\r\n%\r\n% <<rando_6_partial.gif>>\r\n%\r\n%%\r\n% For my final example, the rank of the 8-by-8 magic square is only 3.\r\n% |LUTool| with partial pivoting encounters five negligible pivots.\r\n% The first three columns of |L| and the first three rows of |U|\r\n% are all that is required to reconstruct the original magic square.\r\n%\r\n% <<magic_8_partial.gif>>\r\n%\r\n\r\n%% Software\r\n% A self-extracting archive of |LUTool| is available from\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/LUTool_mzip.m this link>\r\n##### SOURCE END ##### 39dca6aaf7274169876a8296cc5c2505\r\n-->\r\n","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/LUTool_ico.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction-->\r\n<p>\r\n<tt>LUTool<\/tt> provides an interactive animation of Gaussian elimination, the most important algorithm in technical computing.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2025\/02\/08\/lutool-animation-of-gaussian-elimination\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":12377,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,23,9,6,16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12359"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=12359"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12359\/revisions"}],"predecessor-version":[{"id":12362,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12359\/revisions\/12362"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/12377"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=12359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=12359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=12359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}