Geodesic
Computational complexity of generalized $K_N$-convolutions and the fast Vandermonde transform algorithm
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 30 (1990) no. 11, pp. 1625-1637 
A. M. Krot. Computational complexity of generalized $K_N$-convolutions and the fast Vandermonde transform algorithm. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 30 (1990) no. 11, pp. 1625-1637. http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_11_a2/
@article{ZVMMF_1990_30_11_a2,
     author = {A. M. Krot},
     title = {Computational complexity of generalized $K_N$-convolutions and the fast {Vandermonde} transform algorithm},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1625--1637},
     year = {1990},
     volume = {30},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_11_a2/}
}
TY  - JOUR
AU  - A. M. Krot
TI  - Computational complexity of generalized $K_N$-convolutions and the fast Vandermonde transform algorithm
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 1990
SP  - 1625
EP  - 1637
VL  - 30
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_11_a2/
LA  - ru
ID  - ZVMMF_1990_30_11_a2
ER  - 
%0 Journal Article
%A A. M. Krot
%T Computational complexity of generalized $K_N$-convolutions and the fast Vandermonde transform algorithm
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 1990
%P 1625-1637
%V 30
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_1990_30_11_a2/
%G ru
%F ZVMMF_1990_30_11_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

A lemma on the minimum multiplicative complexity of the reduction operation for polynomials whose coefficients are not in the field of constants in Winograd's sense is proved. The lemma is used to prove theorems on the minimum number of multiplications necessary to compute the generalized $K_N$-convolution and on the existence of a fast Vandermonde transform (FVT) algorithm. An $O(2N\log_2^2N)$ $N$-point algorithm is synthesized.

[1] Samarskii A. A., Nikolaev E. S., Metody resheniya setochnykh uravnenii, Nauka, M., 1978 | MR

[2] Winograd S., “Arithmetic complexity of computation”, CBMS-NSF Regional Conf. Series in Appl. Math., SIAM, Philadelphia, 1980 | MR | Zbl

[3] Grigorev D. Yu., Slisenko A. O. (red.), Teoriya slozhnosti vychislenii, Nauka, L., 1982 | MR

[4] Makarov O. M., Vvedenie v teoriyu optimizatsii vychislenii bilineinykh form, Nauk. dumka, Kiev, 1983 | MR

[5] Nussbaumer G., Bystroe preobrazovanie Fure i algoritmy vychisleniya svertok, Radio i svyaz, M., 1985 | MR | Zbl

[6] Krishna H., Computation complexity of bilinear forms, Springer, Berlin etc., 1987 | MR

[7] Voevodin V. V., Tyrtyshnikov E. E., Vychislitelnye protsessy s teplitsevymi matritsami, Nauka, M., 1987 | MR | Zbl

[8] Makklellan Dzh. X., Reider Ch. M., Primenenie teorii chisel v tsifrovoi obrabotke signalov, Radio i svyaz, M., 1983

[9] Bleikhut R., Bystrye algoritmy tsifrovoi obrabotki signalov, Mir, M., 1989 | MR

[10] Winograd S., “On the multiplicative complexity of the discrete Fourier transform”, Advances Math., 32:2 (1979), 83–117 | DOI | MR | Zbl

[11] Duhamel P., Hollman H., “Existence of a $2^n$FFT algorithm with a number of multiplications lower than $2^{n+1}$”, Electronics Letts., 20:17 (1984), 690–692 | DOI

[12] Heideman M. T., Burrus C. S., “On the number of multiplication necessary to compute a length-2 DFT”, IEEE Trans. ASSP, 34:1 (1986), 91–95 | DOI | MR

[13] Krot A. M., “Ob odnom klasse operatorov obobschennogo sdviga v teorii signalov i sistem”, Radiotekhn. i elektronika, 31:8 (1986), 1563–1570 | MR

[14] Krot A. M., “Analiz lineinykh dinamicheskikh sistem na osnove polinomialnykh preobrazovanii chislovykh posledovatelnostei”, Radiotekhn. i elektronika, 33:7 (1988), 1458–1466

[15] Pissanetski S., Tekhnologiya razrezhennykh matrits, Mir, M., 1988 | MR

[16] Knut D., Iskusstvo programmirovaniya dlya EVM, v. 2, Mir, M., 1977 | Zbl

[17] Krot A. M., Minervina E. B., “Algoritmy bystrogo preobrazovaniya Fure dlya deistvitelnykh i ermitovo-simmetrichnykh posledovatelnostei”, Radiotekhn. i elektronika, 34:2 (1989), 369–376

[18] Krot A. M., “Metod sobstvennykh preobrazovanii v razlichnykh polyakh dlya vychisleniya tsiklicheskikh svertok i diskretnogo preobrazovaniya Fure”, Zh. vychisl. matem. i matem. fiz., 29:5 (1989), 675–692 | MR

[19] Belaga E. G., “O vychislenii znachenii mnogochlenov ot odnogo peremennogo s predvaritelnoi obrabotkoi koeffitsientov”, Probl. kibernetiki, 5, 1961, 7–15 | Zbl

[20] Pan V. Ya., “O sposobakh vychisleniya znachenii mnogochlenov”, Uspekhi matem. nauk, 21:1 (127) (1966), 103–134 | MR | Zbl

[21] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[22] Ilin V. P., Kuznetsov Yu. I., Algebraicheskie osnovy chislennogo analiza, Nauka, Novosibirsk, 1986 | MR

[23] Duhamel P., Vetterli M., “Improved Fourier and Hartley transform algorithms: application to cyclic convolution of real data”, IEEE Trans. ASSP, 35:6 (1987), 818–824 | DOI