Разработка и исследование аппаратурно-ориентированных алгоритмов для нахождения собственных значений матриц
Диссертация
Основным математическим аппаратом для решения задач цифровой обработки сигналов является аппарат линейной алгебры. Важнейшими задачами линейной алгебры являются задача решения системы линейных алгебраических уравнений (СЛАУ), задачи разложения матриц на множители с заданными свойствами, сингулярное разложение матриц и определение сингулярных чисел и соответствующих им сингулярных векторов… Читать ещё >
Содержание
- ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ
- 1. ВВЕДЕНИЕ
- 2. ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ
- 2. 1. Анализ требований, предъявляемых к вычислительным системам при нахождении собственных значений матриц
- 2. 2. Псевдоевклидовы и псевдоунитарные преобразования
- 2. 3. Класс алгоритмов дискретных линейных преобразований
- 2. 4. Выводы
- 3. СИНТЕЗ АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ НАХОЖДЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ МАТРИЦ
- 3. 1. Задача нахождения собственных значений матриц
- 3. 2. Алгоритм нахождения собственных значений матриц модифицированным методом Якоби
- 3. 3. Алгоритм нахождения собственных значений матриц методом гиперболических вращений
- 3. 4. Алгоритм нахождения собственных значений матриц методом псевдоотражений
- 3. 5. Алгоритмы для нахождения собственных значений комплексных матриц
- 3. 6. Анализ сходимости синтезированных алгоритмов
- 3. 7. Выводы
- 4. РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ПОДДЕРЖКИ СИНТЕЗА И МОДЕЛИРОВАНИЯ АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ НАХОЖДЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ МАТРИЦ
- 4. 1. Формулирование требований к программному обеспечению
- 4. 2. Визуализация процесса нахождения собственных значений матриц
- 4. 3. Выводы
- 5. РЕАЛИЗАЦИЯ АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ НАХОЖДЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ МАТРИЦ
- 5. 1. Анализ способов реализации синтезированных алгоритмов
- 5. 2. Разработка структурных схем блоков, реализующих алгоритмы нахождения собственных значений
- 5. 3. Сравнительный анализ производительности и аппаратурной сложности устройств для реализации разработанных алгоритмов
- 5. 4. Выводы
Список литературы
- Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров: Учеб. пособие. М.: Высш. шк., 1994. — 544 с.
- А. с. 734 703 СССР, МКИ в 06? 15/20. Устройство для преобразования компонент тензора / Духнич Е. И. № 2 571 966/18−24- Заяв. 23.01.78- Опубл. 16.05.80, Бюл. № 18- Приоритет 15.05.80. — 5 с.
- А. с. 741 274 СССР, МКИ О 06 Б 15/34. Устройство для вычисления синусно-косинусных произведений / Духнич Е. И., Митраков В. А. -2 571 967/18−24- Заяв. 23.01.78- Опубл. 18.06.80, Бюл. № 22- Приоритет 15.06.80.-4 с.
- А. с. 1 142 830 СССР, МКИ в 06? 7/544. Устройство для определения модуля трехмерного вектора / Духнич Е. И. 3 592 736/24−24- Заяв. 18.05.83- Опубл. 28.02.85, Бюл. № 8.-5 с.
- Байков В. Д., Смолов В. В. Аппаратурная реализация элементарных функций в ЦВМ. Л.: Изд-во Ленинградского ун-та, 1975. — 91с.
- Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры. М.: Радио и связь, 1985. — 228 с.
- Беклкмишев Д. В. Курс аналитической геометрии и линейной алгебры. -М.: Наука, 1971.-328 с.
- Воеводин. В. В. Вычислительные основы линейной алгебры. М.: Наука, 1977.-303 с.
- Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984.-318 с.
- Выжиковски Р., Каневский Ю. С., Лепеха В. Л. Параллельные структуры для решения симметричной проблемы собственных значений // Электронное моделирование. 1991. — № 4. — С. 37−43.
- Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. — 576 с.
- Деревенсков С. О. Быстрый ДЛП-алгоритм многомерного вращения вектора / Волгоград, гос. техн. ун-т. Волгоград, 1995. — 4 с. — Деп. в ВИНИТИ № 2442.
- Духнич Е. И. Алгоритмы быстрого преобразования Якоби для многопроцессорной реализации. // Микропроцессорные вычислительные структуры: Сб. Таганрог, 1989. — Вып. 11. — С. 64−66.
- Духнич Е. И. Аппаратурно-ориентированные алгоритмы быстрого преобразования Хаусхолдера // Б8РА-98: Труды межд. конф. М., 1998. -С. 181−186.
- Духнич Е. И. Два обобщенных алгоритма дискретных линейных преобразований // Многопроцессорные вычислительные структуры. -Таганрог, 1984. Вып. 6. — С. 9−11.
- Духнич Е. И. Класс алгоритмов для реализации процедур линейной алгебры с помощью комплекта СБИС // Многопроцессорные вычислительные структуры. Таганрог, 1991. — Вып. 13(XXII). — С. 25−28.
- Духнич Е. И. Класс аппаратурно-реализованных алгоритмов для построения проблемно-ориентированных процессоров с новой архитектурой // Computers-89. Bratislava, Chechoslovakia, 1989. — P. 42−47.
- Духнич E. И. Об одном подходе к выполнению цифровых линейных преобразований // Кибернетика. 1981. — № 5. — С. 97−98.
- Духнич Е. И. Синтез класса алгоритмов и вычислительных структур для реализации дискретных линейных преобразований.: Дис.. д. т. н. -Таганрог, 1985. 306 с.
- Духнич Е. И., Андреев А. Е. Алгоритм для аппаратурной реализации комплексного вращения // Тезисы докладов I межвузовской научно-практической конференции студентов и молодых ученых г. Волжского / ВПИ ВолгГТУ Волжский, 1995. — С. 107−109.
- Духнич Е. И., Андреев Е. А. Модифицированный алгоритм дискретного линейного преобразования гиперболического вращения // Концептуальное проектирование в образовании, техники и технологии: Сб. науч. тр. / ВолгГТУ. Волгоград, 1997. — С. 39−42.
- Духнич Е. И., Андреев А. Е., Стрельников О. И. Применение псевдоунитарных преобразований для нахождения собственных значений матриц // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. Волгоград, 2000. — С. 53−57.
- Духнич Е. И., Деревенсков С. О. ДЛП-алгоритмы многомерных вращений для СБИС-реализации // Многопроцессорные вычислительные структуры: Междуведомственный тематический научный сборник / ТРТИ. Таганрог, 1995.-Вып. 15−16.-С. 25−27.
- Духнич Е. И., Егунов В. А. Алгоритмы многомерных отражений, ориентированные на систолическую реализацию // Проектирование ЭВМ: Межвузовский сборник научных трудов / РГРА. Рязань, 1994. — С. 57−63.
- Духнич Е. И., Егунов В. А. Расширение области сходимости процесса ДЛП-отражения / Волгоград, гос. техн. ун-т. Волгоград, 1995. — 7 с.-Деп. в ВИНИТИ № 2529.
- Духнич Е. И., Лукашева Г. Н., Серов А. А. Модифицированные алгоритмы дискретных линейных преобразований вращения // Многопроцессорные вычислительные структуры. Таганрог, 1990. — Вып.12 (XXI). — С. 37−38.
- Духнич Е. И., Мурашов С. В. Два варианта алгоритмов для быстрой аппаратурной реализации линейного преобразования отражения // Проектирование ЭВМ: Межвуз. сб. научн. трудов. Рязань, 1992. — С. 4751.
- Егунов В. А. Разработка и исследование аппаратурно-ориентированных алгоритмов быстрого преобразования Хаусхолдера: Дис.. к. т. н. -Волгоград, 1996. 199 с.
- Каляев А. В., Духнич Е. И. Алгоритмы для аппаратурной реализации преобразования компонентов тензоров // Автоматика (Рига). 1977. — № 2. — С. 79−82.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. -М.: Наука, 1978. 832 с.
- Кун С. Матричные процессоры на СБИС: Пер. с англ. М.: Машиностроение, 1990. — 672 с.
- Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ.- М.: Мир, 1991. 367 с.
- Параллельный алгоритм Волдера для операции поворота и его применение в машинной графике / Е. И. Артамонов, Ш.-М. А. Исмаилов, О. Г. Кокаев, В. Н. Хачумов // Управляющие системы и машины. 1990. -№ 1. — С. 106−109.
- Парлетт Б. Симметричная проблема собственных значений. Численные методы. М.: Наука, 1983. — 384 с.
- Пат. 1 790 787 РФ, МПК 5 G 06 F 15/347. Устройство для решения задач на собственные значения. / Р. Выжиковский, Ю. С. Каневский, В. JI. Лепеха, М. К. Клименко. № 4 908 183/24- Заявлено 06.02.91- Опубл. 23.01.93 // Изобретения. — 1993. — № 3. — С. 223.
- Пат. 2 007 749 РФ, МПК 5 G 06 F 7/548. Устройство для преобразования координат / Духнич Е. И., Ивахно В. П., Серов А. А. 4 924 087/24- Заяв. 02.04.91- Опубл. 15.02.94, Бюл. № 3. — 6 с.
- Пат. 2 040 039 РФ, МПК 6 G 06 F 7/544. Устройство для определения модуля трехмерного вектора / Духнич Е. И., Серов А. А. № 93 005 835/24- Заяв. 01.02.93- Опубл. 20.07.95, Бюл. № 20. — 5 с.
- Пат. 2 080 650 РФ, МПК 6 G 06 F 7/544. Устройство для вычисления модуля m-мерного вектора / Духнич Е. И., Егунов В. А. № 95 104 370/09- Заявлено 01.03.95- Опубл. 27.05.97 //Изобретения. — 1997. -№ 15. — С. 183.
- Пат. 2 117 987 РФ, МПК G 06 F 17/16. Устройство для вычисления собственных значений (п-п) матриц. / Якуш В. П., Смирнов В. А. № 93 025 204/09- Заявлено 28.04.93- Опубл. 20.08.98 // Изобретения. — 1998. -№ 23.-С 408−410.
- Пат. 2 125 291 РФ, МПК G 06 F 17/14. Устройство для вычисления скользящего спектра / Духнич Е. И., Силантьев Г. В. № 98 104 872/09- Заявлено 24.02.98- Опубл. 20.01.99 // Изобретения. — 1999. — № 2. — С. 549 550.
- Пат. 2 168 760 РФ, МПК 7 G 06 F 17/16, 7/544. Устройство для вычисления собственных значений матриц / Духнич Е. И., Стрельников О. И. № 2 000 100 287/09- Заяв. 05.01.2000- Опубл. 10.06.2001, Бюл. № 16 — 10 с.
- Претт У. Цифровая обработка изображений. М: Наука, 1982.
- Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ. / Под ред. С. Гуна, X. Уайтхауза, Т. Кайлата. М.: Радио и связь, 1989.-472 с.
- Систолические структуры: Пер. с англ. / Под ред. У. Мура, Э. Маккейба, Р. Уркхарта. М.: Радио и связь, 1993. — 416 с.
- Стрельников О. И. Аппаратурно-ориентированные алгоритмы нахождения собственных чисел действительных матриц // Региональная конференция студентов и молодых учёных: Тезисы докладов. Волгоград, 1996. — С. 8788.
- Стренг Г. Линейная алгебра и ее применения: Пер. с англ. М.: Мир, 1980.-454 с.
- Уилкинсон Д. X., Райнш К. Справочник алгоритмов на языке АЛГОЛ. М.: Машиностроение, 1976. 390 с.
- Хорн Р., Джонсон Ч. Матричный анализ. М.: Наука, 1989. — 665 с.
- Шевцов Г. С. Линейная алгебра: Учеб. пособие. М.: Гарданики, 1999. -360 с.
- Шишкин Е. В. Линейные пространства и отображения. М.: Изд-во МГУ, 1987−311 с.
- Ahmed Н.М., Delosme J.-M., Morf M. Highly Concurrent Computing Structures for Matrix Arithmetic and Signal Processing. // IEEE Computer. -1982.-Nl.-P. 65−82.
- Bajard J.-C., Kla S., Muller J.-M. BKM. A New Hardware Algorithm for Complex Elementary Functions // IEEE Transactions on Computers. 1994. -Vol. 43(8).-P. 955−963.
- Brent R. P., Luk F. T. The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays // SIAM J. Scientific and Statistical Computing. 1985. — Vol. 6, No. 1. — P. 69−84.
- Cavallaro J. R., Luk F. T. CORDIC Arithmetic for an SVD Processor. // Journal of Parallel and Disributed Computing. 1988. -N5. — P. 271−290.
- Configuring FLEX 1 OK Devices / Altera Corporation. 1998. — 25 P.
- Doukhnitch E., Strelnikov O., Andreev A. Application of Kronecker Matrix Product for the Synthesis of Hardware-oriented DSP Algorithms // Digital
- Signal Processing and its Applications DSPA-99. Moscow, 1999. — V. 1. — P. 281−282.
- Dupart J., Muller J.-M. The CORDIC Algorithm: New Results for Fast VLSI Implementation // IEEE TRANS ACTIOS ON COMPUTERS. 1993. — VOL. 42, N2.-P. 351−374.
- FLEXI OK Embedded Programmable Logic Device Family / Altera Corporation.- 1999.- 128 P.
- Gotze J., Paul S., Sauer M. An efficient Jacobi-like algorithm for parallel eigenvalue computation // IEEE Trans, on Computers. 1993. — Vol. 42, N9. -P.1058−1063.
- Hekstra G. J., Deprettere E. F. Floating-point CORDIC. // In Proceedings of the 11th Symposium on Computer Arithmetic / IEEE. 1993. — P. 130−137.
- Hsiao S.-F. Multidimensional CORDIC Algorithms: Ph. D. Dissertation. 1993. -199 p.
- Hsiao S.-F., Delosme J.-M. Householder CORDIC Algorithm. // IEEE Transactions on Computers. 1995. — Vol. 44(8). — P. 990−1001.
- Hsiao S.-F., Delosme J.-M. Parallel Processing of Complex Data Using Quaternion and Pseudo-Quaternion CORDIC Algorithm. // In Proceedings of the ASAP'94 Conf. / University of California. 1994. — P. 125−130.
- Hsiao S.-F., Delosme J.-M. Parallel Singular Value Decomposition of Complex Matrices Using Multidimensional CORDIC Algorithms. // IEEE Trans. On Signal Processing. 1996. — Vol. (3). — P. 256−272.
- Muller J.-M. Discrete Basis and Computation of Elementary Functions // IEEE TRANSACTIONS ON COMPUTERS. 1985. — VOL. c-34, N9. — P. 857−862.
- William R., William P. A system of systolic modules for the MUSIC algoritm // IEEE Trans, on signal processing. 1990. — Vol. 39, N11. — P. 2524−2534.