FAST ALGORITHMS: SCIENCE, ART, CRAFT
Keywords:
fast algorithms, computational informatics, computational structures
Abstract
State contains the results of a study of the specifics, possibilities and advantages of fast algorithms. This paper focuses on the description of the proposed approach for the development of fast algorithms using vector-matrix operations.
Downloads
Download data is not yet available.
References
1. Гашков С.Б. Занимательная компьютерная арифметика. Быстрые алгоритмы операций с числами и многочленами / Гашков С.Б. ‒ М.: Книжный дом «ЛИБРОКОМ», 2012. ‒ 224 с.
2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигна-лов: Пер. с англ. ‒ М.: Мир, 1989. ‒ 448 с.
3. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР, 1962. ‒ Т. 145. − № 2.
4. Гриценко С.А. Научные достижения Анатолия Алексеевича Карацубы / С.А. Гриценко, Е.А. Карацуба, М.А. Королëв, И.С. Резвякова, Д.И. Толев, М.Е. Чанга // Совр. пробл. математики: Математика и информатика, 1. − 2012. ‒ Т. 16. ‒ С. 7-30.
5. Кули Льюис Уэлч. Исторические замечания относительно быстрого преобразования Фурье // ТИИЭР. − 1967. ‒ Т. 55. − № 10. ‒ С. 18-21.
6. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. − М.: Радио и связь, 1985. ‒ 248 с.
7. Хуанг Т.С., Эклунд Дж. О., Нуссбаумер Г. Быстрые алгоритмы в цифровой обработке изображений. − М.: Радио и связь, 1984. ‒220 с.
8. Макклеллан Дж.Г., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. − М.: Радио и связь, 1983. ‒ 264 с.
9. Рабин М.О., Виноград Ш. Быстрое вычисление многочленов с предварительной рациональной обработкой коэффициентов // Математика. − 1974. ‒ Т. 18. − Вып. 4. ‒ С. 98-120.
10. Strassen V., Gaussian Elimination is not Optimal // Numer. Math — Springer Science+Business Media. − 1969. ‒ Vol. 13. − № 4. ‒ Р. 354-356.
11. Окулов С.М. Алгоритмы компьютерной арифметики // С.М. Окулов, А.В. Лялин, О.А. Пестов, Е.В. Разова. − 2-е изд. (эл.). − М.: Лаборатория знаний, 2015. ‒ 288 с.
12. Cariow A. Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products // Journal of Signal Processing Theory and Applications. − 2014. ‒ Vol. 3. ‒ № 1. ‒ Р. 1-19.
13. Cariow A. Algorytmiczne aspekty racjonalizacji obliczeń w cyf-rowym przetwarzaniu sygnałów. Wydawnictwo Uczelniane ZUT / PPH ZAPOL Dmochowski Sobczyk Spółka Jawna, 2011. ‒ 230 c.
14. Andreatto B., Cariow A., Automatic generation of fast algorithms for matrix-vector multiplication // International Journal of Computer Mathematics. − 2017. ‒ Р. 1-19.
15. Gliszczyński M., Cariow A. Szybki algorytm splotu kołowego dla N = 2m // Pomiary Automatyka Kontrola. − 2009. ‒ 55. ‒ № 8. ‒ Р. 566-568.
16. Cariow A., Cariowa G. Aspekty algorytmiczne redukcji liczby bloków mnożących w układzie do obliczania iloczynu dwóch kwaternionów // Pomiary, Automatyka, Kontrola. 2010. ‒ Р. 688-690.
17. Cariow A., Cariowa G. Aspekty algorytmiczne organizacji jednostki procesorowej do mnożenia liczb Cayleya // Elektronika: konstrukcje, technologie, zastosowania. − 2010. ‒ 51. ‒ № 11. ‒ S. 104-108.
18. Царёв A.П., Царёва Г.Д. Алгоритм умножения октонионов: Известия Вузов // Радиоэлектроника. − 2012. ‒ Т. 55. ‒ № 10. ‒ С. 44-54.
19. Cariow A., Cariowa G. An algorithm for complex-valued vector-matrix multiplication // Electrical Review. − 2012. ‒ P. 88. ‒ № 10 b. ‒ Р. 213-216.
20. Majorkowska-Mech D., Cariow A. An algorithm for discrete fractional Hadamad transform with reduced arithmetical complexity // Electrical Review. − 2012. ‒ R 88. ‒ № 11 a. ‒ Р. 70-76.
21. Cariow A., Gliszczyński M. Fast algorithms to compute matrix-vector products for Toeplitz and Hankel matrices // Electrical Review. − 2012. ‒ R 88. ‒ № 8. ‒ Р. 166-171.
22. Cariow A., Cariowa G. An algorithm for fast multiplication of sedenions // Information Processing Letters. − 2013. ‒ Р. 324-331.
23. Cariow A., Cariowa G. An algorithm for multiplication of Dirac numbers // Journal of Theoretical and Applied Computer Science. − 2013. ‒ № 4. ‒ Р. 26-34.
24. Cariow A., Cariowa G. Algorithmic tricks for reducing the complexity of FDWT/IDWT basic operations implementation // International Journal of Image, Graphics and Signal Processing. − 2014. ‒ № 10. ‒ Р.1-9.
25. Cariow A., Cariowa G. An algorithm for fast multiplication of Pauli numbers. Advances in Applied Clifford Algebras, 2015. ‒ Р. 1-11.
26. Cariow A., Majorkowska-Mech D. Fast algorithm for discrete fractional Hadamard transform. Numerical Algorithms, 2015. ‒ Vol. 68. ‒ № 3. ‒ Р. 585-600.
27. Cariow A., Cariowa G. On the Multiplication of Biquaternions, Soft Computing in Computer and Information Science: Advances in Intelligent Systems and Computing, 2015. ‒ Vol. 342. ‒ Р. 423-434.
28. Cariow A., Cariowa G., Witczak M. A FPGA-Oriented Fully Parallel Algorithm for multiplying dual quaternions, Measurement Automation Monitoring, Jul. 2015. ‒ Vol. 61. ‒ № 07. ‒ Р. 370-372.
2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигна-лов: Пер. с англ. ‒ М.: Мир, 1989. ‒ 448 с.
3. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР, 1962. ‒ Т. 145. − № 2.
4. Гриценко С.А. Научные достижения Анатолия Алексеевича Карацубы / С.А. Гриценко, Е.А. Карацуба, М.А. Королëв, И.С. Резвякова, Д.И. Толев, М.Е. Чанга // Совр. пробл. математики: Математика и информатика, 1. − 2012. ‒ Т. 16. ‒ С. 7-30.
5. Кули Льюис Уэлч. Исторические замечания относительно быстрого преобразования Фурье // ТИИЭР. − 1967. ‒ Т. 55. − № 10. ‒ С. 18-21.
6. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. − М.: Радио и связь, 1985. ‒ 248 с.
7. Хуанг Т.С., Эклунд Дж. О., Нуссбаумер Г. Быстрые алгоритмы в цифровой обработке изображений. − М.: Радио и связь, 1984. ‒220 с.
8. Макклеллан Дж.Г., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. − М.: Радио и связь, 1983. ‒ 264 с.
9. Рабин М.О., Виноград Ш. Быстрое вычисление многочленов с предварительной рациональной обработкой коэффициентов // Математика. − 1974. ‒ Т. 18. − Вып. 4. ‒ С. 98-120.
10. Strassen V., Gaussian Elimination is not Optimal // Numer. Math — Springer Science+Business Media. − 1969. ‒ Vol. 13. − № 4. ‒ Р. 354-356.
11. Окулов С.М. Алгоритмы компьютерной арифметики // С.М. Окулов, А.В. Лялин, О.А. Пестов, Е.В. Разова. − 2-е изд. (эл.). − М.: Лаборатория знаний, 2015. ‒ 288 с.
12. Cariow A. Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products // Journal of Signal Processing Theory and Applications. − 2014. ‒ Vol. 3. ‒ № 1. ‒ Р. 1-19.
13. Cariow A. Algorytmiczne aspekty racjonalizacji obliczeń w cyf-rowym przetwarzaniu sygnałów. Wydawnictwo Uczelniane ZUT / PPH ZAPOL Dmochowski Sobczyk Spółka Jawna, 2011. ‒ 230 c.
14. Andreatto B., Cariow A., Automatic generation of fast algorithms for matrix-vector multiplication // International Journal of Computer Mathematics. − 2017. ‒ Р. 1-19.
15. Gliszczyński M., Cariow A. Szybki algorytm splotu kołowego dla N = 2m // Pomiary Automatyka Kontrola. − 2009. ‒ 55. ‒ № 8. ‒ Р. 566-568.
16. Cariow A., Cariowa G. Aspekty algorytmiczne redukcji liczby bloków mnożących w układzie do obliczania iloczynu dwóch kwaternionów // Pomiary, Automatyka, Kontrola. 2010. ‒ Р. 688-690.
17. Cariow A., Cariowa G. Aspekty algorytmiczne organizacji jednostki procesorowej do mnożenia liczb Cayleya // Elektronika: konstrukcje, technologie, zastosowania. − 2010. ‒ 51. ‒ № 11. ‒ S. 104-108.
18. Царёв A.П., Царёва Г.Д. Алгоритм умножения октонионов: Известия Вузов // Радиоэлектроника. − 2012. ‒ Т. 55. ‒ № 10. ‒ С. 44-54.
19. Cariow A., Cariowa G. An algorithm for complex-valued vector-matrix multiplication // Electrical Review. − 2012. ‒ P. 88. ‒ № 10 b. ‒ Р. 213-216.
20. Majorkowska-Mech D., Cariow A. An algorithm for discrete fractional Hadamad transform with reduced arithmetical complexity // Electrical Review. − 2012. ‒ R 88. ‒ № 11 a. ‒ Р. 70-76.
21. Cariow A., Gliszczyński M. Fast algorithms to compute matrix-vector products for Toeplitz and Hankel matrices // Electrical Review. − 2012. ‒ R 88. ‒ № 8. ‒ Р. 166-171.
22. Cariow A., Cariowa G. An algorithm for fast multiplication of sedenions // Information Processing Letters. − 2013. ‒ Р. 324-331.
23. Cariow A., Cariowa G. An algorithm for multiplication of Dirac numbers // Journal of Theoretical and Applied Computer Science. − 2013. ‒ № 4. ‒ Р. 26-34.
24. Cariow A., Cariowa G. Algorithmic tricks for reducing the complexity of FDWT/IDWT basic operations implementation // International Journal of Image, Graphics and Signal Processing. − 2014. ‒ № 10. ‒ Р.1-9.
25. Cariow A., Cariowa G. An algorithm for fast multiplication of Pauli numbers. Advances in Applied Clifford Algebras, 2015. ‒ Р. 1-11.
26. Cariow A., Majorkowska-Mech D. Fast algorithm for discrete fractional Hadamard transform. Numerical Algorithms, 2015. ‒ Vol. 68. ‒ № 3. ‒ Р. 585-600.
27. Cariow A., Cariowa G. On the Multiplication of Biquaternions, Soft Computing in Computer and Information Science: Advances in Intelligent Systems and Computing, 2015. ‒ Vol. 342. ‒ Р. 423-434.
28. Cariow A., Cariowa G., Witczak M. A FPGA-Oriented Fully Parallel Algorithm for multiplying dual quaternions, Measurement Automation Monitoring, Jul. 2015. ‒ Vol. 61. ‒ № 07. ‒ Р. 370-372.
Published
2017-09-27
How to Cite
ЦАРЁВ, А. (2017). FAST ALGORITHMS: SCIENCE, ART, CRAFT. Transport Development, (1(1), 5-11. https://doi.org/10.33082/td.2017.1-1.01
Section
COMPUTER NETWORKS, TELECOMMUNICATION TECHNOLOGIES
This work is licensed under a Creative Commons Attribution 4.0 International License.
