于外积秩为1的Cholesky分解可通过对矩阵做如下划分得到
Av
这里
vBv
T
10TI
10Bvv0
vTI
1

且因是A正定的故0而BvvT是XTAX的主子阵其中
1vTXI
10
T故它也是正定的如果存在Cholesky分解G1G1
BvvT则由426有AGGT其中
0G1
Gv
因此可通过反复利用来得到最终的Cholesky分解其方向和kji形式的高斯消去法一样算法Cholesky分解基于外积运算给定一对称正定阵AR


本算法计算满足AGG的下三角阵
T
f
GR
对所有的ijGij覆盖Aij
Fork1
Akk
Akk
Ak1
kAk1
kAkkForjk1
Aj
jAj
jAj
kAjkE
dE
d本算法需
3flops注意其中的j循环计算外积的下三角部分Ak1
k1
Ak1
k1
Ak1
kAk1
kT回想在Gaxpy运算和外积运算的比较容易得知Gaxpy运算中读写向量的次数要比外积运算中少一半
3
基于分块点积的Cholesky分解假定A


对称正定将AAij和其Cholesky因子看作含有方块对角块的NN分块阵取出等式
AGGT中关于第Ij块i≥j的等式有
AijGikGjk
Tk1j
定义SAijTT
GG
k1ik
j1
Tjk
则有当ij时GjjGjjS当ij时GijGjjS通过合适的排序这些方程可用来求得所有的Gij算法Cholesky基于分块点积运算给定一个对称正定阵AR
T


本算法可求得一个下三角阵GR



满足AGGA的下三角部分被G覆盖A被看作是含方对角块的NN分块阵Forj1NForijNS
Aij

G
k1
j1
ik
TGik
Ifij计算Cholesky分解SElse从GijGjjS解出GijE
d用Gij覆盖Aij
T
GG
k1ik
j1
Tik
fE
dE
d整个算法需
33flops与前述其他形式的Cholesky算法相同假定A被适当分块则本算法中含有大量的矩阵乘法运算例如如果
rN且每个都是RR的则3级运算量约占11N由于没有给出基于gaxpy运算的Cholesky算法得出。将基于gaxpy的Cholesky分解执行r步后，我们已知
2
A11A21
A12G11A22G21
0IrI
r0
0G11AG21
0I
1
T

rrrr中的G11R
和G21R
。再接下来我们不对A，而是对已明显形成具有可利用的对称结构的约化后
T的矩阵进行另外的r步基于gaxpy的Cholesky计算。按此方法进行下去，我们得到基于分块AA22G21G22
的Cholesky计r