Page 157 - Matrices theory and applications

8. Matrix Factorizations
140
8.1.2 Complexity of Matrix Inversion
We can now show that the complexity of inverting a matrix is not higher
than that of matrix multiplication, at equivalent sizes. We assume here that
k = IR or CC.
Notation 8.1.1 We denote by J n the number of operations in k used in
the inversion of an n × n matrix, and by P n the number of operations (in
k) used in the product of two n × n matrices.
Of course, the number J n must be understood for generic matrices, that
is, for matrices within a dense open subset of M n (k). More important,
J n ,P n also depend on the algorithm chosen for inversion or for multipli-
cation. In the sequel we wish to adapt the inversion algorithm to the one
used for multiplication.
k
Let us examine first of all the matrices whose size n has the form 2 .
We decompose the matrices M ∈ GL n (k) blockwise, with blocks of size
n/2 × n/2. The condition A ∈ GL n/2 (k) defines a dense open set, since
M → det A is a nonzero polynomial. Suppose that we are given an inver-
sion algorithm for generic matrices in GL n/2 (k)in j k−1 operations. Then
blockwise LU factorization and the formula M −1 = U −1 L −1 furnish an
inversion algorithm for generic matrices in GL n (k). We can then bound
j k by means of j k−1 and the number π k−1 = P 2 k−1 of operations used in
the computation of the product of two matrices of size 2 k−1 × 2 k−1 .We
shall denote also by σ k =2 2k the number of operations involved in the
computation of the sum of matrices in M k(k).
2
To compute M −1 , we first compute A −1 ,then CA −1 ,which gives us
L −1 in j k−1 + π k−1 operations. Then we compute (D − CA −1 B) −1 (this
amounts to σ k−1 + π k−1 + j k−1 operations) and A −1 B(D − CA −1 B) −1
(cost: 2π k−1 ), which furnishes U −1 . The computation of U −1 L −1 is done
at the cost σ k−1 +2π k−1 . Finally,

j k ≤ 2j k−1 +2σ k−1 +6π k−1 .
In other words,
2 −k j k − 2 1−k j k−1 ≤ 2 k−1 +3 · 2 1−k π k−1 . (8.1)
The complexity of the product in M n (k) obeys the inequalities
2
2
n ≤ P n ≤ n (2n − 1).
2
The first inequality is due to the number of data (2n ) and the fact that
each operation involves only two of them. The second is given by the naive
2
algorithm that consists in computing n scalar products.
Lemma 8.1.1 If P n ≤ c α n α (with 2 ≤ α ≤ 3), then j l ≤ C α π l ,where
C α =1 + 3c α /(2 α−1 − 1).
It is enough to sum (8.1) from k =1 to l and use the inequality 1 + q +
l
··· + q l−1 ≤ q /(q − 1) for q> 1.