Information Technology Reference
In-Depth Information
j
=
i
−
n
+
1
+
r
and 0
≤
r
≤
2
n
−
2. A generic Toeplitz matrix
T
is shown below:
⎡
⎣
⎤
⎦
a
n−
1
a
n
a
n
+
1
...
a
2
n−
2
a
n−
2
a
n−
1
a
n
...
a
2
n−
3
a
n−
3
a
n−
2
a
n−
1
...
a
2
n−
4
T
=
.
.
.
.
.
.
.
a
0
a
1
a
2
...
a
n−
1
n
circulant matrix
C
has the property that the entries on the
k
th row are a right
cyclic shift by
k
An
n
×
−
1 places of the entries on the first row, as suggested below.
⎡
⎤
a
0
a
1
a
2
...
a
n−
1
⎣
⎦
a
n−
1
a
0
a
1
...
a
n−
2
a
n−
2
a
n−
1
a
0
...
a
n−
3
C
=
.
.
.
.
.
.
.
a
1
a
2
a
3
...
a
0
The circulant is a type of Toeplitz matrix. Thus the function defined by the product of a
Toeplitz matrix and a vector contains as a subfunction the function defined by the product of
a circulant matrix and a vector. Consequently, any algorithm to multiply a vector by a Toeplitz
matrix can be used to multiply a circulant by a vector.
As stated in Section
2.11
,a
permutation
π
:
R
n
→R
n
of an
n
-tuple
x
=(
x
1
,
x
2
,
...
,
x
n
)
over the set
R
is a rearrangement
π
(
x
)=(
x
π
(
1
)
,
x
π
(
2
)
,
...
,
x
π
(
n
)
)
of the components
of
x
.A
n
×
n
permutation matrix
P
has entries from the set
{
}
0, 1
(here 0 and 1 are the
R
identities under addition and multiplication for a ring
) with the property that each row
and column of
P
has exactly one instance of 1. (See the example below.) Let
A
be an
n
n
matrix. Then
AP
contains the columns of
A
in a permuted order determined by
P
. A similar
statement applies to
PA
. Shown below is a permutation matrix
P
and the result of multiplying
it on the right by a matrix
A
on the left. In this case
P
interchanges the first two columns of
A
.
⎡
⎣
×
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
1234
5678
9101112
13
0100
1000
0010
0001
2134
6578
10
=
9
11
12
14
15
16
14
13
15
16
6.3 Matrix Multiplication
Matrix multiplication is defined in Section
6.2
.The
standard matrix multiplication algo-
rithm
computes the matrix product using the formula for
c
i
,
j
givenin(
6.1
). It performs
nmp
multiplications and
n
(
m
1
)
p
additions. As shown in Section
6.3.1
, however, matrices can
be multiplied with many fewer operations.
Boolean matrix multiplication
is matrix multiplication for matrices over
−
B
when
+
de-
notes
OR
and
∗
denotes
AND
. Another example is matrix multiplication over the set of integers
Search WWH ::
Custom Search