as consequence of theorem the solution to the linear system ax can be computed in ( ntime via- - cd [ bif pthe sherman-morrison recursion can frequently be much faster than the ( direct solution via the lu decomposition method in section in summarythe following algorithm computes the matrices and in theorem via the recursion ( algorithm sherman-morrison recursion inputeasily invertible matrix and column vectors - outputmatrices and such that cd- ca- - ck ak for (assuming is diagonal or easily invertible matrix for do dk > ck for do > ck cj cj dk > [ diag( return and finallynote that if is diagonal matrix and we only store the diagonal elements of and (as opposed to storing the full matrices and )then the storage or memory requirements of algorithm are only ( na cholesky decomposition if is real-valued positive definite matrix (and therefore symmetric) covariance matrixthen an lu decomposition can be achieved with matrices and ltheorem cholesky decomposition real-valued positive definite matrix [ai rnxn can be decomposed as llwhere the real lower triangular matrix [lk satisfies the recursive formula - ak = ji lki lk - = ji for and where = ji lki : (