Skip to main content
edited tags
Link
Mr.Wizard
  • 273.1k
  • 34
  • 595
  • 1.4k
edited tags
Link
Tweeted twitter.com/#!/StackMma/status/212221682457382916
Source Link

What's the most "functional" way to do Cholesky decomposition?

I can do Cholesky in a procedural style, such as:

ProceduralCholesky[matrin_List?PositiveDefiniteMatrixQ] := 
 Module[{dimens,
   ll},
  dimens = Length@matrin;
  ll = ConstantArray[0, {dimens, dimens}];
  Do[
   Do[
     If[i == j,
       ll[[i, i]] = 
         Sqrt[matrin[[i, i]] - 
           Sum[Conjugate[#]*# &@ll[[i, k]], {k, 1, i - 1}]];,
       ll[[i, 
          j]] = (matrin[[i, j]] - 
            Sum[ll[[i, k]]*Conjugate[ll[[j, k]]], {k, 1, j - 1}])/
          Conjugate[ll[[j, j]]];];,
     {i, j, dimens}];,
   {j, dimens}];
  ll
  ]

Moreover, I've seen a "half-functional" implementation, which, however, features a Table function and an outer For loop. So far I have managed to address the need for the Table function by writing:

HalfFunctionalCholesky[matrin_List?PositiveDefiniteMatrixQ] := 
 Module[{dimens,
   uu},
  dimens = Length@matrin;
  uu = ConstantArray[0, {dimens, dimens}];
  Do[uu[[i]] = makerow[matrin, i, uu, dimens], {i, dimens}];
  uu
  ]

makerow[matrin_List, rowindex_Integer, uu_, dimens_Integer] := 
 PadLeft[
  (Join[
      {#},
      offdiagonalelements[matrin, uu, rowindex, dimens, #]]) &@
   diagonalelement[matrin, uu, rowindex],
  dimens]

diagonalelement[matrin_, uu_, rowindex_] := 
 Sqrt[matrin[[rowindex, rowindex]] - Conjugate[#].# &@
   uu[[;; (rowindex- 1), rowindex]]]

offdiagonalelements[matrin_, uu_, rowindex_, dimens_, 
  diag_] := (matrin[[rowindex, (rowindex+ 1) ;; dimens]] -
    Conjugate[
      uu[[;; (rowindex - 1), 
       rowindex]]].uu[[;; (rowindex - 1), (rowindex + 1) ;; 
       dimens]])/diag

I am not satisfied yet. Can I avoid using the outer Do loop by turning it into a Fold or a Nest? The only idea I was able to come up with involved a Nested ReplacePart function, but I think it would be just some pretentious sweeping under the rug. Am I mistaken?

Thank you in advance!