| Preface | p. xi |
| Acknowledgments | p. xiii |
| Introduction | p. 1 |
| Introduction to fast algorithms | p. 1 |
| Applications of fast algorithms | p. 6 |
| Number systems for computation | p. 8 |
| Digital signal processing | p. 9 |
| History of fast signal-processing algorithms | p. 17 |
| Introduction to abstract algebra | p. 21 |
| Groups | p. 21 |
| Rings | p. 26 |
| Fields | p. 30 |
| Vector space | p. 34 |
| Matrix algebra | p. 37 |
| The integer ring | p. 44 |
| Polynomial rings | p. 48 |
| The Chinese remainder theorem | p. 58 |
| Fast algorithms for the discrete Fourier transform | p. 68 |
| The Cooley-Tukey fast Fourier transform | p. 68 |
| Small-radix Cooley-Tukey algorithms | p. 72 |
| The Good-Thomas fast Fourier transform | p. 80 |
| The Goertzel algorithm | p. 83 |
| The discrete cosine transform | p. 85 |
| Fourier transforms computed by using convolutions | p. 91 |
| The Rader-Winograd algorithm | p. 97 |
| The Winograd small fast Fourier transform | p. 102 |
| Fast algorithms based on doubling strategies | p. 115 |
| Halving and doubling strategies | p. 115 |
| Data Structures | p. 119 |
| Fast algorithms for sorting | p. 120 |
| Fast transposition | p. 122 |
| Matrix multiplication | p. 124 |
| Computation of trigonometric functions | p. 127 |
| An accelerated euclidean algorithm for polynomials | p. 130 |
| A recursive radix-two fast Fourier transform | p. 139 |
| Fast algorithms for short convolutions | p. 145 |
| Cyclic convolution and linear convolution | p. 145 |
| The Cook-Toom algorithm | p. 148 |
| Winograd short convolution algorithms | p. 155 |
| Design of short linear convolution algorithms | p. 164 |
| Polynomial products modulo a polynomial | p. 168 |
| Design of short cyclic convolution algorithms | p. 171 |
| Convolution in general fields and rings | p. 176 |
| Complexity of convolution algorithms | p. 178 |
| Architecture of filters and transforms | p. 194 |
| Convolution by sections | p. 194 |
| Algorithms for short filter sections | p. 199 |
| Iterated filter sections | p. 202 |
| Symmetric and skew-symmetric filters | p. 207 |
| Decimating and interpolating filters | p. 213 |
| Construction of transform computers | p. 216 |
| Limited-range Fourier transforms | p. 221 |
| Autocorrelation and crosscorrelation | p. 222 |
| Fast algorithms for solving Toeplitz Systems | p. 231 |
| The Levinson and Durbin algorithms | p. 231 |
| The Trench algorithm | p. 239 |
| Methods based on the euclidean algorithm | p. 245 |
| The Berlekamp-Massey algorithm | p. 249 |
| An accelerated Berlekamp-Massey algorithm | p. 255 |
| Fast algorithms for trellis search | p. 262 |
| Trellis and tree searching | p. 262 |
| The Viterbi algorithm | p. 267 |
| Sequential algorithms | p. 270 |
| The Fano algorithm | p. 274 |
| The stack algorithm | p. 278 |
| The Bahl algorithm | p. 280 |
| Numbers and fields | p. 286 |
| Elementary number theory | p. 286 |
| Fields based on the integer ring | p. 293 |
| Fields based on polynomial rings | p. 296 |
| Minimal polynomials and conjugates | p. 299 |
| Cyclotomic polynomials | p. 300 |
| Primitive elements | p. 304 |
| Algebraic integers | p. 306 |
| Computation in finite fields and rings | p. 311 |
| Convolution in surrogate fields | p. 311 |
| Fermat number transforms | p. 314 |
| Mersenne number transforms | p. 317 |
| Arithmetic in a modular integer ring | p. 320 |
| Convolution algorithms in finite fields | p. 324 |
| Fourier transform algorithms in finite fields | p. 328 |
| Complex convolution in surrogate fields | p. 331 |
| Integer ring transforms | p. 336 |
| Chevillat number transforms | p. 339 |
| The Preparata-Sarwate algorithm | p. 339 |
| Fast algorithms and multidimensional convolutions | p. 345 |
| Nested convolution algorithms | p. 345 |
| The Agarwal-Cooley convolution algorithm | p. 350 |
| Splitting algorithms | p. 357 |
| Iterated algorithms | p. 362 |
| Polynomial representation of extension fields | p. 368 |
| Convolution with polynomial transforms | p. 371 |
| The Nussbaumer polynomial transforms | p. 372 |
| Fast convolution of polynomials | p. 376 |
| Fast algorithms and multidimensional transforms | p. 384 |
| Small-radix Cooley-Tukey algorithms | p. 384 |
| The two-dimensional discrete cosine transform | p. 389 |
| Nested transform algorithms | p. 391 |
| The Winograd large fast Fourier transform | p. 395 |
| The Johnson-Burrus fast Fourier transform | p. 399 |
| Splitting algorithms | p. 403 |
| An improved Winograd fast Fourier transform | p. 410 |
| The Nussbaumer-Quandalle permutation algorithm | p. 411 |
| A collection of cyclic convolution algorithms | p. 427 |
| A collection of Winograd small FFT algorithms | p. 435 |
| Bibliography | p. 442 |
| Index | p. 449 |
| Table of Contents provided by Ingram. All Rights Reserved. |
