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

Given a linear system of n equations in the column vector x of n unknowns defined by
the non-singular n

× n coefficient matrix M and the vector b ,namely,

M x = b

(6.5)

the solution x can be obtained through a matrix-vector multiplication with M − 1 :
x = M − 1 b

In this section we present two algorithms for matrix inversion. Such algorithms compute
the (partial) matrix inverse function f ( n )

n 2 n 2

A − 1 :

R →R

that maps non-singular n

× n

R

matrices over a field onto their inverses. The first result, Theorem 6.5.4 ,demonstratesthat

C Ω f ( n )

A − 1 =Θ( M matrix ( n , K )) with a circuit whose depth is more than linear in n .The
second, Theorem 6.5.6 ,demonstratesthat D Ω f ( n )

A − 1 = O (log 2 n ) with a circuit whose size

is O ( nM matrix ( n , K )) .
Before describing the two matrix inversion algorithms, we present a result demonstrating
that matrix multiplication of n 3 n matrix; the

function defining the former task is a subfunction of the function defining the latter task.

× n matrices is no harder than inverting a 3 n ×

LEMMA 6.5.1 The matrix inverse function f ( 3 n )

A − 1 contains as a subfunction the function f ( n )

A×B :

2 n 2 n 2

R →R that maps two matrices over R to their product.

Proof The proof follows by writing a 3 n n matrices

and then specializing the entries to be the identity matrix I , the zero matrix 0, or matrices
A and B :

× 3 n matrix as a 3 × 3matrixof n ×

⎡
⎣

⎤
⎦

⎡
⎣

⎤
⎦

− 1

IA 0
0 IB
00 I

I − AAB

= 0 B

00 I

I −

This identity is established by showing that the product of these two matrices is the identity
matrix.

6.5.1 Symmetric Positive Definite Matrices
Our first algorithm to invert a non-singular n n matrix M has a circuit size linear in

M matrix ( n , K ) , which, in light of Lemma 6.5.1 , is optimal to within a constant multiplicative
factor. This algorithm makes use of symmetric positive definite matrices, the Schur comple-
ment, and LDL T factorization, terms defined below. This algorithm has depth O ( n log 2 n ) .
The second algorithm, Csanky's algorithm, has circuit depth O (log 2 n ) , which is smaller,
but circuit size O ( nM matrix ( n , K )) , which is larger. Symmetric positive definite matrices are
defined below.

×

DEFINITION 6.5.1 Amatrix M is positive definite if for all non-zero vectors x the following
condition holds:

x T M x =
1 ≤i , j≤n

x i m i , j x j > 0

(6.6)

Amatrixis symmetric positive definite (SPD) if it is both symmetric and positive definite.