next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc :: LUdecomposition

LUdecomposition -- LU decomposition

Synopsis

Description

The output matrices are mutable exactly when the input matrix is, but the matrix A is not modified

If Q is the m by m permutation matrix such that Q_(P_i,i) = 1, and all other entries are zero, then A = QLU.

There are several restrictions. The first is that there are only a limited number of rings for which this function is implemented. Second, if A is a mutable matrix defined over RR or CC, then A must be densely encoded. This restriction is not present if A is a matrix.

i1 : kk = ZZ/101

o1 = kk

o1 : QuotientRing
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
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
i4 : Q = id_(kk^3) _ P

o4 = | 1 0 0 |
     | 0 1 0 |
     | 0 0 1 |

              3        3
o4 : Matrix kk  <--- kk
i5 : Q * L * U == matrix A

o5 = true
For matrices over RR or CC, this function calls the lapack routines, which are restricted to 53 bits of precision.
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
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
i8 : Q = id_ (RR^3) _ P

o8 = | 0 0 1 |
     | 0 1 0 |
     | 1 0 0 |

                3          3
o8 : Matrix RR    <--- RR
              53         53
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
i10 : clean(1e-15,oo)

o10 = 0

                 3          6
o10 : Matrix RR    <--- RR
               53         53
Mutable matrices can sometimes be useful for speed, and/or space. If A is a mutable matrix, it must be densely encoded (which is the default).
i11 : A = mutableMatrix(CC,5,10, Dense=>true)

o11 = 0

o11 : MutableMatrix
i12 : printingPrecision = 2

o12 = 2
i13 : setRandomSeed 0

o13 = 0
i14 : fillMatrix A

o14 = | .89+.67i .91+.31i .35+.56i .19+.4i  .28+.61i .03+.51i .44+.64i  .47+.4i  .48+.82i  .5+.15i  |
      | .29+.63i .07+.81i .25+.15i .62+.02i .97+.68i .15+.66i .19+.52i  .16+.71i .98+.06i  .47+.77i |
      | .03+.71i .36+.71i .83+.54i .22+.39i .91+.89i .17+.63i .99+.57i  .91+.57i .065+.28i .31+.54i |
      | .89+.23i .13+.25i .87+.42i .56+.87i .17+.97i .35+.38i .18+.37i  .31+.73i .98+.21i  .21+.28i |
      | .46+.78i .74+.11i .61+.85i .7+.68i  .07+.88i .24+.12i .34+.062i .56+.63i .59+.83i  .1+.61i  |

o14 : MutableMatrix
i15 : (P,L,U) = LUdecomposition A;
i16 : Q = id_(CC^5) _ P

o16 = | 1 0 0 0 0 |
      | 0 0 0 0 1 |
      | 0 0 1 0 0 |
      | 0 1 0 0 0 |
      | 0 0 0 1 0 |

                 5          5
o16 : Matrix CC    <--- CC
               53         53
i17 : matrix Q * matrix L * matrix U - matrix A

o17 = | 0         0        0 0                 0                
      | 5.6e-17   -5.6e-17 0 -1.1e-16+1.7e-16i -2.2e-16         
      | 5.6e-17   0        0 -2.8e-17          0                
      | -1.1e-16i 0        0 0                 0                
      | -1.1e-16i 0        0 0                 -2.8e-17+1.1e-16i
      -----------------------------------------------------------------------
      0                 0       0         0 0        |
      -2.8e-17          0       0         0 1.1e-16i |
      0                 1.1e-16 1.1e-16   0 0        |
      0                 0       0         0 0        |
      -2.8e-17-5.6e-17i 0       -1.1e-16i 0 0        |

                 5          10
o17 : Matrix CC    <--- CC
               53         53
i18 : clean(1e-15,oo)

o18 = 0

                 5          10
o18 : Matrix CC    <--- CC
               53         53

Caveat

This function is limited in scope, but is sometimes useful for very large matrices

See also

Ways to use LUdecomposition :