Information Technology Reference
In-Depth Information
Winograd [
364
] demonstrated that matrix multiplication is no harder than matrix inver-
sion, whereas Aho, Hopcroft, and Ullman [
10
] demonstrated the converse.
Csanky's algorithm for matrix inversion is reported in [
82
]. Leverrier's method for com-
puting the characteristic function of a matrix is described in [
98
].
Although the FFT algorithm became well known through the work of Cooley and Tukey
[
80
], the idea actually begins with Gauss in 1805! (See Heideman, Johnson, and Burrus [
130
].)
The zero-one principle for the study of comparator networks is due to Knuth [
170
]. Oddly
enough, Batcher's odd-even merging network is due to Batcher [
29
].
Borodin and Munro [
56
] is a good early source for arithmetic complexity, the size and
depth of arithmetic circuits for problems related to matrices and polynomials. More recent
work on the parallel evaluation of arithmetic circuits is surveyed by JaJ´a[
148
,Chapter8]and
von zur Gathen [
111
].
Search WWH ::
Custom Search