Information Technology Reference
In-Depth Information
b) Compute the LDL T decomposition of M T M .
c) Solve the system ( 6.15 ) by solving three subsequent systems:
LDL T x = b
(6.15)
L u = b
(6.16)
D v = u
(6.17)
L T x = v
(6.18)
Clearly, L u = LD v = LDL T x = b .
The vector b is formed by a matrix-vector multiplication that can be done with n 2 mul-
tiplications and n ( n
1 ) additions, for a total of 2 n 2
n operations.
Since L is unit lower triangular, the system ( 6.16 )issolvedby forward elimination .The
value of u 1 is b 1 . The value of u 2 is b 1
l 2,1 u 1 , obtained by eliminating u 1 from the sec-
ond equation. Similarly, on the j th step, the values of u 1 , u 2 , ... , u j− 1 are known and their
weighted values can be subtracted from b j
to provide the value of u j ;thatis,
u j = b j
l j ,1 u 1
l j ,2 u 2 −···−
l j , j− 1 u j− 1
j
n .Here n ( n
1 ) / 2productsareformedand n ( n
1 ) / 2 subtractions taken for
for 1
a total of n ( n
1 ) operations.
Since D is diagonal, the system ( 6.17 ) is solved for v by multiplying u j by the multiplica-
tive inverse of d j , j ;thatis,
v j = u j d 1
j , j
for 1
n . This is called normalization .Here n divisions are performed.
Finally, the system ( 6.18 ) is solved for x by backward substitution ,whichisforward
elimination applied to the elements of x in reverse order.
j
THEOREM 6.6.1 Let f ( n )
SPD solve : R n 2 + n
R n be the (partial) function that computes the
solution to a linear system of equations defined by an n
×
n symmetric positive definite coefficient
matrix M .Then
C ( f ( n )
C ( f ( n )
LDL T )+ O ( n 2 )
SPD solve )
D ( f ( n )
C ( f ( n )
LDL T )+ O ( n )
If M is not SPD but is non-singular, an additional O ( M matrix ( n , K )) circuit elements and
depth O (log n ) suffice to compute it.
SPD solve )
6.7 Convolution and the FFT Algorithm
The discrete Fourier transform (DFT) and convolution are widely used techniques with im-
portant applications in signal processing and computer science.
In this section we introduce the DFT, describe the fast Fourier transform algorithm, and
derive the convolution theorem. The naive DFT algorithm on sequences of length n uses
O ( n 2 ) operations; the fast Fourier transform algorithm uses only O ( n log n ) operations, a
saving of a factor of at least 100 for n
1, 000. The convolution theorem provides a way
to use the DFT to convolve two sequences in O ( n log n ) steps, many fewer than the naive
algorithm for convolution, which uses O ( n 2 ) steps.
 
Search WWH ::




Custom Search