Winograd S. Arithmetic Complexity of Computations

Society for Industrial and Applied Mathematics, 1980, -99 p.The two major problem areas which are the concern of Arithmetic Complexity of Computations are:
What is the minimum number of arithmetic operations which are needed to perform the computation?
How can we obtain a better algorithm when improvement is possible?
These two questions are very large in scope, since they pertain to any computation which is arithmetic in nature. In these lectures we will not attempt to cover the whole theory, but concentrate on a narrower class of computational problems — that of computing a system of bilinear forms (sums of values a_ijkx_iy_j on i and j). As we will see later, there are many problems of practical interest which can be viewed as computing a system of bilinear forms. Yet finding the most efficient algorithm for computing a system of bilinear forms can be most vexing. In spite of the apparent simplicity of systems of bilinear forms many of the problems connected with their computations have not been solved.
In developing these lectures we will try to keep a balance between the mathematical aspects of the theory and the applicability of the results. We will emphasize the results which lead to applications in the area of signal processing. This choice was motivated by several reasons: Many signal processing problems place a very heavy computational load on even the largest computers which are available, thus even a modest reduction in their execution time may have practical significance. Secondly, the results which are applicable to signal processing are relatively new and consequently do not appear in any of the books on computational complexity which are available, but are scattered in journal articles. Last, and not least, the choice of the material which was made gives a good indication of the flavor of complexity of computation (admittedly at the expense of indicating its full scope).
In the next section, we will describe three algorithms which were discovered in the last two decades and which were the motivation for much of the development in complexity of computations. The following section will provide a general background of the basic results, and the next three sections will deal with the complexity of computing convolution, digital filtering, and the discrete Fourier transform.
I would like to end this introductory section with another qualification. Even though the title speaks of arithmetic complexity, that is the consideration of both the number of additions and the number of multiplications, we will concentrate our attention on the number of multiplications. The main reason is that the theory concerning the number of multiplications is much more developed than that of the number of additions. However, in the discussion of some of the applications we will have to pay attention to the number of additions, and not just to the number of multiplications.Three Examples
General Background
Product of Polynomials
FIR Filters
Product of Polynomials Modulo a Polynomial
Cyclic Convolution and Discrete Fourier Transform