<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>LUdecomposition -- LU decomposition</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="___Make__Documentation.html">next</a> | <a href="___Lower__Bound.html">previous</a> | <a href="___Make__Documentation.html">forward</a> | <a href="___Lower__Bound.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>LUdecomposition -- LU decomposition</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>(P,L,U) = LUdecomposition A</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>A</tt>, <span>a <a href="___Mutable__Matrix.html">mutable matrix</a></span>, or <span>a <a href="___Matrix.html">matrix</a></span>,of size <tt>m</tt> by <tt>n</tt>, over a a finite field <tt>ZZ/p</tt>, <a href="___R__R.html" title="the class of all real numbers">RR</a> or <a href="___C__C.html" title="the class of all complex numbers">CC</a></span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>P</tt>, <span>a <a href="___List.html">list</a></span>, of integers in [0, ..., m-1] forming a permutation</span></li>
<li><span><tt>L</tt>, <span>a <a href="___Mutable__Matrix.html">mutable matrix</a></span>, or <span>a <a href="___Matrix.html">matrix</a></span>, an m by min(m,n) lower triangular matrix, with 1's on the diagonal</span></li>
<li><span><tt>U</tt>, <span>a <a href="___Mutable__Matrix.html">mutable matrix</a></span>, or <span>a <a href="___Matrix.html">matrix</a></span>, a min(m,n) by n upper triangular matrix</span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div>The output matrices are mutable exactly when the input matrix is, but the matrix <tt>A</tt> is not modified<p/>
If <tt>Q</tt> is the <tt>m</tt> by <tt>m</tt> permutation matrix such that <tt>Q_(P_i,i) = 1</tt>, and all other entries are zero, then <tt>A = QLU</tt>. <p/>
There are several restrictions. The first is that there are only a limited number of rings for which this function is implemented. Second, if <tt>A</tt> is a mutable matrix defined over <tt>RR</tt> or <tt>CC</tt>, then <tt>A</tt> must be densely encoded. This restriction is not present if <tt>A</tt> is <span>a <a href="___Matrix.html">matrix</a></span>.<p/>
<table class="examples"><tr><td><pre>i1 : kk = ZZ/101
o1 = kk
o1 : QuotientRing</pre>
</td></tr>
<tr><td><pre>i2 : A = matrix"1,2,3,4;1,3,6,10;19,7,11,13" ** kk
o2 = | 1 2 3 4 |
| 1 3 6 10 |
| 19 7 11 13 |
3 4
o2 : Matrix kk <--- kk</pre>
</td></tr>
<tr><td><pre>i3 : (P,L,U) = LUdecomposition A
o3 = ({0, 1, 2}, | 1 0 0 |, | 1 2 3 4 |)
| 1 1 0 | | 0 1 3 6 |
| 19 -31 1 | | 0 0 47 22 |
o3 : Sequence</pre>
</td></tr>
<tr><td><pre>i4 : Q = id_(kk^3) _ P
o4 = | 1 0 0 |
| 0 1 0 |
| 0 0 1 |
3 3
o4 : Matrix kk <--- kk</pre>
</td></tr>
<tr><td><pre>i5 : Q * L * U == matrix A
o5 = true</pre>
</td></tr>
</table>
For matrices over <tt>RR</tt> or <tt>CC</tt>, this function calls the lapack routines, which are restricted to 53 bits of precision.<table class="examples"><tr><td><pre>i6 : A = matrix"1,2,3,4,5,6;1,3,6,12,13,16;19,7,11,47,48,21" ** RR
o6 = | 1 2 3 4 5 6 |
| 1 3 6 12 13 16 |
| 19 7 11 47 48 21 |
3 6
o6 : Matrix RR <--- RR
53 53</pre>
</td></tr>
<tr><td><pre>i7 : (P,L,U) = LUdecomposition A
o7 = ({2, 1, 0}, | 1 0 0 |, | 19 7 11 47 48
| .0526316 1 0 | | 0 2.63158 5.42105 9.52632 10.4737
| .0526316 .62 1 | | 0 0 -.94 -4.38 -4.02
------------------------------------------------------------------------
21 |)
14.8947 |
-4.34 |
o7 : Sequence</pre>
</td></tr>
<tr><td><pre>i8 : Q = id_ (RR^3) _ P
o8 = | 0 0 1 |
| 0 1 0 |
| 1 0 0 |
3 3
o8 : Matrix RR <--- RR
53 53</pre>
</td></tr>
<tr><td><pre>i9 : Q * L * U - A
o9 = | 0 -2.22045e-16 0 0 0 0 |
| 0 0 0 0 0 0 |
| 0 0 0 0 0 0 |
3 6
o9 : Matrix RR <--- RR
53 53</pre>
</td></tr>
<tr><td><pre>i10 : clean(1e-15,oo)
o10 = 0
3 6
o10 : Matrix RR <--- RR
53 53</pre>
</td></tr>
</table>
Mutable matrices can sometimes be useful for speed, and/or space. If <tt>A</tt> is a mutable matrix, it must be densely encoded (which is the default).<table class="examples"><tr><td><pre>i11 : A = mutableMatrix(CC,5,10, Dense=>true)
o11 = 0
o11 : MutableMatrix</pre>
</td></tr>
<tr><td><pre>i12 : printingPrecision = 2
o12 = 2</pre>
</td></tr>
<tr><td><pre>i13 : setRandomSeed 0
o13 = 0</pre>
</td></tr>
<tr><td><pre>i14 : fillMatrix A
o14 = | .83+.27i .64+.14i .014+.33i .12+.86i .76+.02i .41+.088i .12+.78i .98+.79i .4+.12i .06+.57i |
| .44+.48i .45+.077i .12+.72i .8+.77i .19+.73i .014+.18i .97+.42i .05+.55i .18+.53i 1+.32i |
| .084+.19i .4+.52i .13+.28i .88+.03i .3+.49i .86+.04i .7+.5i .7+.78i .37+.41i .56+.16i |
| .83+.04i .34+.26i .39+.97i .4+.6i .77+.28i .9+.84i .73+.88i .23+.99i .56+.89i .3+i |
| .88+.44i .24+.77i .82+.62i .32+.7i .39+.49i .58+.45i .94+.87i .19+.85i .093+.017i .34+.83i |
o14 : MutableMatrix</pre>
</td></tr>
<tr><td><pre>i15 : (P,L,U) = LUdecomposition A;</pre>
</td></tr>
<tr><td><pre>i16 : Q = id_(CC^5) _ P
o16 = | 0 0 0 0 1 |
| 0 1 0 0 0 |
| 0 0 0 1 0 |
| 0 0 1 0 0 |
| 1 0 0 0 0 |
5 5
o16 : Matrix CC <--- CC
53 53</pre>
</td></tr>
<tr><td><pre>i17 : matrix Q * matrix L * matrix U - matrix A
o17 = | -1.1e-16 0 -2.2e-16+5.6e-17i 0 0
| 0 0 8.3e-17-1.1e-16i 0 0
| -2.8e-17i -1.1e-16i 5.6e-17 0 0
| -1.1e-16-5.6e-17i 5.6e-17+5.6e-17i 0 0 0
| 0 0 0 0 0
-----------------------------------------------------------------------
0 -2.2e-16+1.1e-16i 1.1e-16 0
2.8e-17+5.6e-17i -5.6e-17i 0 0
-1.1e-16+2.8e-17i 1.1e-16i -1.1e-16 -5.6e-17-5.6e-17i
0 -1.1e-16 2.8e-17-1.1e-16i 0
0 0 0 0
-----------------------------------------------------------------------
0 |
1.1e-16-1.1e-16i |
-1.7e-16i |
-1.1e-16i |
0 |
5 10
o17 : Matrix CC <--- CC
53 53</pre>
</td></tr>
<tr><td><pre>i18 : clean(1e-15,oo)
o18 = 0
5 10
o18 : Matrix CC <--- CC
53 53</pre>
</td></tr>
</table>
</div>
</div>
<div class="single"><h2>Caveat</h2>
<div>This function is limited in scope, but is sometimes useful for very large matrices</div>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_solve.html" title="solve a linear equation">solve</a> -- solve a linear equation</span></li>
<li><span><a href="___S__V__D.html" title="singular value decomposition of a matrix">SVD</a> -- singular value decomposition of a matrix</span></li>
<li><span><a href="___Mutable__Matrix.html" title="the class of all mutable matrices">MutableMatrix</a> -- the class of all mutable matrices</span></li>
<li><span><a href="_fill__Matrix.html" title="fill a mutable matrix with random numbers">fillMatrix</a> -- fill a mutable matrix with random numbers</span></li>
<li><span><a href="_clean.html" title="Set to zero elements that are approximately zero">clean</a> -- Set to zero elements that are approximately zero</span></li>
<li><span><a href="_norm.html" title="">norm</a></span></li>
</ul>
</div>
<div class="waystouse"><h2>Ways to use <tt>LUdecomposition</tt> :</h2>
<ul><li>LUdecomposition(Matrix)</li>
<li>LUdecomposition(MutableMatrix)</li>
</ul>
</div>
</div>
</body>
</html>
