6.1 LDU Factor Update

Algorithm 8 follows the lead of our sources (see Section 6.3 for details) and implements a technique for updating the factors L, D, and U of A following a rank one change to A.

Algorithm 8: LDU Factor Update
for i=1,,ni=1,\cdots,n
   δ=di\delta=d_{i}
   p=yip=y_{i}
   q=ziq=z_{i}
   di=di+αpqd_{i}=d_{i}+\alpha pq
   β1=αpdi\beta_{1}=\displaystyle\frac{\alpha p}{d_{i}}
   β2=αqdi\beta_{2}=\displaystyle\frac{\alpha q}{d_{i}}
   α=αδdi\alpha=\displaystyle\frac{\alpha\delta}{d_{i}}
   for j=i+1,,nj=i+1,\cdots,n
      yj=yj-pljiy_{j}=y_{j}-pl_{ji}
      zj=zj-quijz_{j}=z_{j}-qu_{ij}
      lji=lji+β1yjl_{ji}=l_{ji}+\beta_{1}y_{j}
      uij=uij+β2yju_{ij}=u_{ij}+\beta_{2}y_{j}

The scalar α\alpha and the vectors y and zT are destroyed by this procedure. The factors of A are overwritten by their new values.

The outer loop of Algorithm 8 does not have to begin at one unless y is full. If y has any leading zeros, the initial value of i should be the index of yi the first nonzero element of y. If there is no a priori information about the structure of y but there is a high probability of leading zeros, testing yi for zero at the beginning of the loop might save a lot of work. However, you must remember to cancel the test as soon as a nonzero yi is encountered.