Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 258

M 2,1 M − 1

1,1 M 1,2

L 2 D 2

MULT [ n/ 2 ]

Tr a n s p o s e

M 2,1 ( L − 1 ) T D − 1

LDL T [ n/ 2]

1

SCALE [ n/ 2 ]

M 2,1 M − 1

S = M 2,2 −

1,1 M 1,2

M 2,1 ( L − 1 ) T

SUB [ n/ 2 ]

MULT [ n/ 2 ]

M 2,2

Tr a n s p o s e

M 2,1

L − 1
1

TRI INV [ n/ 2 ]

L 1 D 1

LDL T [ n/ 2]

M 1,1

Figure 6.6 An algebraic circuit to produce the LDL

T factorization of an SPD matrix.

1,1 M 1,2 can be formed by multiplying M 2,1 L − 1 T D − 1

M 2,1 M − 1 • S = M 2,2 −

1 by the
transpose of M 2,1 L − 1 T using MULT [ n/ 2 ] and subtracting the result from M 2,2 by the
subtraction operator SUB [ n/ 2 ] .

The LDL T • factorization of the n/ 2 × n/ 2matrix S is computed using the procedure

LDL T [ n/ 2] to produce the n/ 2 × n/ 2 triangular and diagonal matrices L 2 and D 2 ,re-

spectively.

Let's now determine the size and depth of circuits to implement the algorithm for LDL T [ n ].
Let f ( n )

n 2 ( n 2 + n ) / 2 be the function defined by the LDL T factorization of an n

R →R × n

LDL T :

SPD matrix, f ( n )

( n 2 + n ) / 2 ( n 2 + n ) / 2 be the inversion of an n

R →R × n lower triangular

tri inv :

matrix, f ( n )

n 2 + n n 2

be the computation of N ( D − 1 ) for an n

scale :

R →R × n matrix N and

adiagonalmatrix D , f ( n )

2 n 2

n 2 be the multiplication of two n

mult :

R →R × n matrices, and

f ( n )

2 n 2 n 2

sub :

R →R the subtraction of two n × n matrices. Since a transposition can be done