Arithmetic complexity of computations / Shmuel Winograd.

Format:

Book

Author/Creator:

Winograd, S.

Contributor:

Society for Industrial and Applied Mathematics.

Series:

CBMS-NSF regional conference series in applied mathematics ; 33.

CBMS-NSF regional conference series in applied mathematics ; 33

Language:

English

Subjects (All):

Bilinear forms--Data processing.

Bilinear forms.

Computational complexity.

Physical Description:

1 online resource (93 p. )

Place of Publication:

Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 1980.

Language Note:

English

System Details:

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Summary:

Focuses on finding the minimum number of arithmetic operations needed to perform the computation and on finding a better algorithm when improvement is possible. The author concentrates on that class of problems concerned with computing a system of bilinear forms. Results that lead to applications in the area of signal processing are emphasized, since (1) even a modest reduction in the execution time of signal processing problems could have practical significance; (2) results in this area are relatively new and are scattered in journal articles; and (3) this emphasis indicates the flavor of complexity of computation.

Contents:

Three examples

General background

Product of polynomials

FIR filters

Product of polynomials modulo a polynomial

Cyclic convolution and discrete Fourier transform.

Notes:

"Based on lectures given by the author at the University of Pittsburgh."

Includes bibliographical references (p. 93).

Title from title screen, viewed 04/05/2011.

ISBN:

1-61197-036-9

Publisher Number:

CB33 SIAM