Multiplicative Complexity, Convolution, and the DFT

این کتاب در نظر گرفته شده است که مرجعی جامع به نظریه پیچیدگی ضربی باشد که در محاسبات پردازش سیگنال دیجیتال اعمال می شود. اگرچه چند الگوریتم برای نشان دادن این نظریه گنجانده شده است، اما من بیشتر بر توسعه خود نظریه تمرکز کردم. اشتیاق عفونی هاوی جانسون برای طراحی الگوریتم های DfT کارآمد مرا به این موضوع علاقه مند کرد. من از پروفسور سید بوروس برای تشویق و حمایت من در این تلاش سپاسگزارم. همچنین می‌خواهم از هنریک سورنسن و داگ جونز برای بسیاری از بحث‌های محرک تشکر کنم. بدهی بزرگی به شموئل وینوگراد، که تقریباً به تنهایی، بیشتر نتایج نظری کلیدی را که منجر به این کار حاضر شد، ارائه کرد. تک نگاری او، پیچیدگی حسابی o/محاسبات، من را با مکانیسم پشت برهان قضایا در پیچیدگی ضربی آشنا کرد. من را قادر می سازد به مقالات قبلی او بازگردم و از ظرافت روش های او برای استخراج نظریه قدردانی کنم. دومین کار کلیدی که بر من تأثیر گذاشت، مقاله لوئیس آسلندر و وینوگراد در مورد پیچیدگی ضربی سیستم های نیمه خطی تعریف شده توسط چندجمله ای ها بود. پس از خواندن این مقاله، برای من واضح بود که این نظریه را می توان برای بسیاری از مسائل محاسباتی مهم به کار برد. این تأثیرات را می توان به راحتی در اثر حاضر تشخیص داد.

This book is intended to be a comprehensive reference to multiplicative com­ plexity theory as applied to digital signal processing computations. Although a few algorithms are included to illustrate the theory, I concentrated more on the develop­ ment of the theory itself. Howie Johnson's infectious enthusiasm for designing efficient DfT algorithms got me interested in this subject. I am grateful to Prof. Sid Burrus for encouraging and supporting me in this effort. I would also like to thank Henrik Sorensen and Doug Jones for many stimulating discussions. lowe a great debt to Shmuel Winograd, who, almost singlehandedly, provided most of the key theoretical results that led to this present work. His monograph, Arithmetic Complexity o/Computations, introduced me to the mechanism behind the proofs of theorems in multiplicative complexity. enabling me to return to his earlier papers and appreciate the elegance of his methods for deriving the theory. The second key work that influenced me was the paper by Louis Auslander and Winograd on multiplicative complexity of semilinear systems defined by polynomials. After reading this paper, it was clear to me that this theory could be applied to many impor­ tant computational problems. These influences can be easily discerned in the present work.