![](https://csdnimg.cn/release/download_crawler_static/9104209/bg10.jpg)
4 GAUSSIAN ELIMINATION AND ITS
以
RIANTS
Any time
we
run a computer program,
we
want to know how long it will take
to
complete its task.
If
the job involves large matrices, say 1000 × 1000, it may take a
while. The traditional way to estimate running time is to count how many flops the
computer must perform. Let
us
therefore count the flops in a matrix-vector multiply.
Looking
at
(1.1.7),
we
see that if A
is
n ×
m,
the outer loop will be executed m
times. On each
of
these passes, the inner loop is executed n times. Each execution
of
the inner loop involves two flops. Therefore the total flop count for the algorithm
is
2nm.
This is a particularly easy flop count. On more complex algorithms
it
will
prove useful to use the following device. Replace each loop
by
a summation
sign~.
Since the inner loop is executed for i =
1,
...
, n, and there are two flops per pass, the
n
to
山
mmb
巳
r
of
flops
p 巳
r
m
巳
don
巳川
execution
of
th
巳
inr
i=l
the outer loop runs from j = 1
...
m,
the total number
of
flops is
2:2:2
=汇
2n
=
2nm.
The flop count gives a rough idea
of
how long
it
will take the algorithm to run.
Suppose, for example,
we
have run the algorithm on a 300 × 400 matrix and observed
how long it takes.
If
we
now want to run the same algorithm on a matrix
of
size
600
× 400,
we
expect it to take about twice
as
long, since
we
are doubling n while
holding
m fixed and thereby doubling the flop count
2nm.
Square matrices arise frequently in applications.
If
A is n × n, the flop count for
a matrix-vector multiply is
2η2.
If
we
have performed a matrix-vector multiply on,
say, a 500
× 500 matrix,
we
can expect the same operation on a 1000 × 1000 matrix
to take about four times
as
long, since doubling n quadruples the flop count in this
case.
Ann
× n matrix-vector multiply is an example
of
what
we
call an
0
(
η2)
process,
or a process
of
order n2. This just means that the amount
of
work
is
proportional
to
n
2.
The notation is used
as
a way
of
emphasizing the dependence on n and de-
emphasizing the proportionality constant, which is 2 in this case. Any O(n2) process
has the property that doubling the problem size quadruples the amount
of
work.
It is important to realize that the flop count is only a crude indicator
of
the
amount
of
work that an algorithm entails. It ignores many other tasks that the
computer must perform in the course
of
executing the algorithm. The most important
of
these are fetching data from memory to be operated on and returning data to
memory once the operations are done. On many computers the memory access
operations are slower than the floating point operations, so it makes more sense to
count memory accesses than flops. The flop count
is
useful, nevertheless, because
it
also gives
us
a rough count
of
the memory traffic. For each operation
we
must
fetch operands from memory, and after each operation
we
must return the result
to memory. This is a gross
oversimpli
且
cation
of
what actually goes on in modern
computers. The execution speed
of
the algorithm can be affected drastically by how
the memory traffic is organized.
We
will have more to say about this
at
the end