автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование аппаратурно-ориентированных алгоритмов для нахождения собственных значений матриц

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ.

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. Выводы.

В современной цифровой обработке сигналов большое внимание уделяется так называемым задачам и алгоритмам с высоким разрешением. Примерами таких задач являются определение направления на источник сигнала, обработка сигнала, полученного от фазированной антенной решетки, адаптивное формирование луча и другие. Алгоритмы, лежащие в основе решения данных задач, получили название алгоритмов с высоким разрешением, поскольку качество решения задачи зависит от размерности объектов, обрабатываемых данными алгоритмами. Например, при определении направления на источник сигнала точность получаемых значений (угловых координат источника сигнала), степень размытости диаграмм обработанных данных и прочие параметры, определяющие качество полученных данных, зависят от размерности матриц, соответствующих полученному сигналу. Тот факт, что точность результата зависит в основном не от точности компонентов матрицы, а от размерности, позволяет отнести данную задачу к классу задач с высоким разрешением.

В настоящее время такой фактор ограничения размерности обрабатываемых объектов, как аппаратурные затраты на формирование запоминающей среды, в которой будут храниться компоненты этих объектов, практически полностью утратил свое значение. Для хранения матрицы размером 1000x1000, разрядность компонентов которой составляет 64, необходима память объемом 64Мбит, что существенно ниже степени интеграции современных БИС запоминающих устройств. Гораздо более существенную роль играет время обработки матриц и векторов большого размера. Например, если та же система определения направления на источник сигнала формирует непрерывный поток данных, то основным ограничителем размерности матриц будет время обработки, которое не должно превышать период поступления новых данных на вход вычислительного устройства. Такой режим работы называется режимом реального времени.

Таким образом, качество решения задач с высоким разрешением в системах реального времени зависит от производительности вычислительных систем, на которых решаются данные задачи.

Основным математическим аппаратом для решения задач цифровой обработки сигналов является аппарат линейной алгебры. Важнейшими задачами линейной алгебры являются задача решения системы линейных алгебраических уравнений (СЛАУ), задачи разложения матриц на множители с заданными свойствами, сингулярное разложение матриц и определение сингулярных чисел и соответствующих им сингулярных векторов, нахождение собственных значений матриц и соответствующих им собственных векторов. Задача нахождения собственных значений произвольных матриц является существенно более сложной задачей, чем остальные перечисленные. Эта сложность обусловлена тем, что для нахождения собственных значений несимметричных матриц необходимо выполнять псевдоунитарные преобразования, в отличие от остальных задач, в том числе задачи нахождения собственных значений симметричных матриц, для которых требуется выполнение только унитарных преобразований. Сравнение существующих в настоящее время аппаратурно-ориентированных алгоритмов для реализации унитарных и псевдоунитарных преобразований показывает, что псевдоунитарные алгоритмы обладают значительно худшей сходимостью, чем унитарные. Например, алгоритм CORDIC в режиме кругового вращения сходится без повторения итераций, а в режиме гиперболического сдвига требует повторения ряда итераций [62, 66, 67]. Многомерные алгоритмы отражения по сравнению с алгоритмами псевдоотражений требуют значительно меньшего повторения итераций, а, зачастую, вообще не требуют [66, 67]. Другим недостатком псевдоунитарных преобразований является большие сложности при расширении области сходимости реализующих эти преобразования алгоритмов.

Такая ситуация привела к тому, что при решении задач практики операции нахождения собственных значений матриц заменяются, по возможности, операциями нахождения сингулярных значений [56, 57, 66, 69, 74, 75, 76]. Однако существует ряд задач, где по-прежнему необходимо получение диагональных и блочно-диагональных матриц с собственными значениями исходных матриц в качестве компонентов.

Когда при решении практической задачи необходимо вычисление собственных значений матриц, возникает вопрос о возможностях аппаратуры вычислительной системы, прежде всего центрального процессора, выполнять те или иные операции. Существующие в настоящее время микропроцессоры различаются по уровню операций, которые включены в систему команд данного процессора. На самом нижнем уровне находятся процессоры, которые могут выполнять только самые примитивные логические и поразрядные операции. Как правило, такие процессоры относятся к процессорам с сокращенным набором команда (процессоры с архитектурой RISC), и малое количество операций обусловлено стремлением минимизировать систему команд микропроцессора.

Далее следуют процессоры, которые могут выполнять арифметические операции, причем в разных моделях могут быть реализованы различные операции от аддитивных до мультипликативных и трансцендентных. Данные процессоры относятся к процессорам с архитектурой CISC. Наличие конвейера команд в микропроцессорах данного типа позволяет даже самые сложные арифметические операции выполнять за 1 такт. Развитие этих микропроцессоров привело к созданию процессоров с суперскалярной архитектурой, в которых существует множество конвейеров команд, за счет чего пиковая производительность достигает значения, большего одной команды за такт.

На следующем уровне находятся процессоры, организующие параллельную обработку данных, в которых реализован параллелизм типа "одна команда, много данных" - ОКМД (SIMD). Данные процессоры позволяют выполнять одну и туже арифметическую операцию над массивами аргументов, что ускоряет выполнение матрично-векторных умножений. Современные суперскалярные микропроцессоры содержат в своем составе подобные команды. К наиболее известным наборам команд SIMD современных суперскалярных микропроцессоров относятся команды ММХ, SSE, SSE2 и 3DNow!, реализованные в микропроцессорах компаний Intel и AMD.

Следующим классом микропроцессоров являются процессоры цифровой обработки сигналов - ЦОС (DSP). Первые поколения данных процессоров отличались наличием в системе команд операций свертки (умножения с накоплением), которые позволяли быстро выполнять такие операции, как цифровая фильтрация, скалярное произведение векторов и другие. Современные процессоры ЦОС могут выполнять более сложные команды, например, быстрое преобразование Фурье (БПФ), метод наименьших квадратов.

На следующем уровне находятся специализированные процессоры или спецпроцессоры (ASP), позволяющие решать типовые задачи. К типовым задачам линейной алгебры относятся, например, решение СЛАУ, определение расстояния между векторами, обращение матриц, нахождение сингулярных и собственных значений матриц, операции над тензорами. Спецпроцессоры решают, как правило, одну задачу или семейство сходных задач. Задача, для которой используется спецпроцессор, решается аппаратурно в соответствии с аппаратурно-ориентированным алгоритмом. При проектировании аппаратурного алгоритма учитываются технология СБИС, на базе которых реализуются спецпроцессоры.

Особой возможностью расширения системы команд микропроцессора является проектирование микропроцессоров с длинными инструкциями (архитектура VLIW). Длина одной команды процессора с данной архитектурой может достигать нескольких килобит. Данные процессоры позволяют одной командой закодировать выполнение целого алгоритма, чем может быть достигнута чрезвычайно высокая производительность.

При разработке программных алгоритмов нахождения собственных значений матриц, как правило, полагают, что в системе команд микропроцессора имеются команды для выполнения основных арифметических действий, а также для вычисления некоторых иррациональных и трансцендентных функций, например, тригонометрических, гиперболических, квадратного корня. Подавляющее большинство программных алгоритмов, способных находить все собственные значения матриц, основаны на свойстве преобразования подобия матриц сохранять собственные значения. К программным методам нахождения собственных значений относятся степенной метод и его модификация - степенной метод с исчерпыванием, метод итераций, метод QR-разложения и его модификация - метод QR-разложения со сдвигом, метод Якоби. Все перечисленные методы являются итерационными; получаемая на каждой итерации матрица является подобной исходной; при выполнении последней итерации матрица имеет вид близкий к диагональному или блочно-диагональному. Доказано, что за конечное число итераций ни один из перечисленных методов не позволяет привести произвольную матрицу к диагональному или блочно-диагональному виду, поэтому выполнение алгоритма останавливается, когда полученная матрица отличается от диагональной или блочно диагональной на малую величину, или когда обнаруживается, что алгоритм расходится. Очень эффективным является комбинирование программных методов нахождения собственных значений, когда сначала один алгоритм приводит матрицу к некоторому стандартному виду, чаще всего к трехдиагональной или Хессенберговой матрице, а затем другой алгоритм находит собственные значения полученной матрицы.

Все известные программные методы нахождения собственных значений матриц обобщены в библиотеке Е18РАСК, реализация которой имеется практически для всех платформ. Функции библиотеки Е18РАСК позволяют как находить собственные значения действительных и комплексных матриц, так и приводить обрабатываемые матрицы к некоторому специальному виду, сохраняя собственные значения исходных матриц. Реализация Е18РАСК для конкретной платформы может быть оптимизирована с целью достижения наибольшей производительности при решении задачи нахождения собственных значений матриц на данной платформе. Функции библиотеки Е18РАСК являются удобным программным интерфейсом для доступа к процессорам при нахождении собственных значений матриц.

Задачи практики, в которых требуется нахождение собственных значений матриц, в том числе задачи с высоким разрешением, могут быть решены программно с использованием библиотеки Е1БРАСК на базе универсальных ЭВМ со скалярными или суперскалярными процессорами общего назначения или на базе суперЭВМ. Анализ данных способов реализации показывает их непригодность для ряда практических ситуаций. В частности, процессоры общего назначения не обеспечивают требуемой производительности при решении задачи нахождения собственных значений.

В связи с этим возникает необходимость разработки быстрых и компактных устройств для нахождения собственных значений, реализуемых в виде специализированных процессоров на базе СБИС, а также аппаратурных алгоритмов, лежащих в основе данных устройств.

Как правило, при проектировании устройств, предназначенных для выполнения типовых математических операций, существует корреляция между производительностью устройства и его аппаратурной сложностью. Крайним способом реализации, при котором достигается максимальная производительность и требуются максимальные аппаратурные затраты, является реализация в виде сверхпараллельного вычислительного устройства. Например, сверхпараллельный вычислитель для нахождения собственных значений матриц 10x10 с разрядностью компонентов 32 потребует запоминающей среды объемом ~Ю970 бит, что не реализуемо при современном уровне степени интеграции БИС запоминающих устройств. Однако, для данного класса аппаратурных алгоритмов можно успешно добиваться существенного повышения производительности устройств, реализующих данные алгоритмы, при несущественном увеличении или даже уменьшении аппаратурных затрат.

Проведенный патентный анализ показал, что существующие в настоящее время устройства для аппаратурной реализации задачи нахождения собственных значений матриц [35, 37, 40] обладают рядом недостатков. В частности, разработанные устройства содержат такие блоки, как умножители, делители, блоки определения обратной величины числа, блоки вычисления квадратного корня, которые, с одной стороны, плохо реализуемы аппаратурно, а с другой, отрицательно сказываются на производительности устройств, приближая ее к производительности универсальных процессоров при решении задачи нахождения собственных значений.

В связи с этим возникает задача разработки аппаратурных алгоритмов, состоящих только из простых операций, таких как сложение, сдвиг, вычисление логических функций, и учитывающих технологию производства СБИС. Аппаратурная сложность устройств, реализующих данные алгоритмы, должна быть сравнимой с достигнутой в настоящее время степенью интеграции цифровых микросхем. Производительность таких устройств должна приближаться к производительности суперЭВМ при решении задач нахождения собственных значений матриц.

Предлагаемая работа посвящена синтезу и исследованию аппаратурно-ориентированных алгоритмов дискретных линейных преобразований (ДЛП) для нахождения собственных значений матриц, предназначенных для реализации в виде специализированных процессоров на базе СБИС, а также разработке аппаратурных блоков для реализации синтезированных алгоритмов.

Целью настоящей диссертации является разработка и исследование класса аппаратурно-ориентированных алгоритмов нахождения собственных значений матриц, удовлетворяющих требованиям реализации данных алгоритмов на СБИС и позволяющих в несколько раз уменьшить время нахождения собственных значений матриц по сравнению с существующими устройствами за счет распараллеливания и конвейеризации вычислений.

Формулировка проблемы исследования.

Исследование и синтез аппаратурно-ориентированных алгоритмов для нахождения собственных значений матриц, удовлетворяющих технологии СБИС и позволяющих в несколько раз уменьшить время нахождения собственных значений по сравнению с аппаратной реализацией известных программных методов. Разработка аппаратурных блоков для реализации синтезированных алгоритмов.

Основными направлениями исследования являются:

1) Анализ известных программных методов нахождения собственных значений матриц и их модификация для аппаратурной реализации.

2) Разработка новых аппаратурно-ориентированных алгоритмов нахождения собственных значений матриц.

3) Моделирование полученных аппаратурно-ориентированных алгоритмов и исследование их основных свойств.

4) Сравнение основных характеристик синтезированных алгоритмов с традиционными программными алгоритмами при их аппаратурной реализации, а также при программной реализации этих алгоритмов на скалярных и суперскалярных микропроцессорах.

Перечисленные направления исследований определяют структуру предлагаемой диссертации. Работа состоит из введения, четырех основных разделов, заключения и списка использованной литературы. Во введении показана актуальность темы, сформулированы основные цели исследований, показана научная новизна и практическая ценность полученных результатов.

5.4. Выводы

1. Разработаны структурные схемы блоков для реализации аппаратурно-ориентированных алгоритмов нахождения собственных значений матриц модифицированным методом Якоби, методом гиперболических вращений и методом псевдоотражений, как в виде последовательных устройств, так и в виде конвейеров.

2. Существует два основных варианта реализации: в виде заказных микросхем и на базе программируемых логических интегральных схем (ПЛИС). В первом случае структурные схемы блоков для реализации синтезированных алгоритмов передаются предприятиям, которые производят требуемые СБИС на определенной элементной базе средними или крупными сериями. Преимуществом данного варианта является меньшая стоимость производства одной СБИС, а также большая, при прочих равных условиях, производительность получаемых устройств за счет отсутствия конфигурирующих цепей внутри СБИС. Во втором случае по структурной схеме блока, реализующего синтезированный алгоритм, получают файл конфигурации, который заносится в память ПЛИС и настраивает ее для работы в соответствии с реализуемым алгоритмом. Преимуществом данного варианта реализации является возможность создания макета с целью тестирования и отладки разрабатываемого аппаратурного алгоритма, а также возможность использования одной и той же СБИС для реализации различных алгоритмов в зависимости от решаемой задачи, например, в гиперкомпьютерах. При разработке проекта на языке описания интегральных схем большой степени интеграции VHDL одна и та же проектная документация может использоваться как для реализации разрабатываемых аппаратурных алгоритмов в виде заказных СБИС, так и для конфигурирования ПЛИС.

3. Разрабатываемые спецпроцессоры могут использоваться как в самостоятельных мобильных устройствах, которые должны выполнять большое количество вычислений, так и в интегрированных системах в качестве акселератора (ускорителя) определенных вычислений.

4. Разработано устройство для интеграции спецпроцессора нахождения собственных значений матриц с персональными компьютерами и рабочими станциями. Устройство представляет собой плату расширения PCI, которое может использоваться в рабочих станциях, имеющих соответствующий слот расширения, в качестве акселератора вычислений собственных значений матриц. Важнейшими компонентами платы расширения являются две ПЛИС. Первая - ЕРМ3128ТС100-7 семейства МАХ3000 фирмы Altera - содержит энергонезависимую конфигурационную память и используется в качестве контроллера шины PCI. Вторая - EPF 10К20ТС144-4 семейства FLEX10K фирмы Altera - содержит в качестве конфигурационной памяти статическое ОЗУ и используется как спецпроцессор. Разработанное программное обеспечение позволяет занести содержимое файла со структурной схемой блока одного из синтезированных алгоритмов нахождения собственных значений в конфигурационную память FLEXI OK, после чего в системе становится доступным новое устройство, которое может производить вычисление собственных значений матриц.

5. Разработанное устройство может использоваться как универсальный вычислитель. В любой момент времени в конфигурационную память FLEXI OK можно занести новую схему и продолжать работать с другим устройством. Схема может реализовывать не только алгоритм нахождения собственных значений матриц, но и любой другой алгоритм. Таким образом, плата может быть использована для ускорения любых вычислений, для которых разработан соответствующий аппаратурный алгоритм. Такой принцип вычислений положен в основу гиперкомпьютеров, следовательно, разработанное устройство можно отнести к микрогиперкомпьютерам.

6. Анализ производительности и аппаратурной сложности разработанных устройств показал, что разработанные устройства превосходят по производительности в случае больших размерностей обрабатываемых матриц суперскалярные микропроцессоры. Использование разработанных последовательных устройств позволит в 4-8 раз снизить время решения задачи нахождения собственных значений матриц и в 2-6 раз уменьшить аппаратурные затраты по сравнению с аппаратурной реализацией известных программных алгоритмов при прочих равных условиях, а также в 2-4 раза для матриц размерности 100 или в 400-800 раз для матриц размерности 10000 снизить время решения задачи по сравнению с их решением на универсальных ЭВМ со скалярными и суперскалярными микропроцессорами.

7. Из последовательных устройств наилучшие показатели производительности и аппаратурной сложности имеет устройство, реализующее метод псевдоотражений, поэтому его следует использовать в большинстве случаев. Если область сходимости алгоритма нахождения собственных значений методом псевдоотражений не достаточна, возможно использование других разработанных устройств. Конвейерные устройства следует использовать, когда принципиально важным является обеспечение сверхвысокой производительности, а аппаратурные затраты значения не имеют ввиду наличия избыточного количества аппаратуры.

162

6. ЗАКЛЮЧЕНИЕ

В диссертационной работе разработан и исследован класс аппаратурно-ориентированных алгоритмов дискретных линейных преобразований для нахождения собственных значений матриц.

Основной научный результат состоит в разработке класса аппаратурно-ориентированных алгоритмов для нахождения собственных значений матриц. Предложенные алгоритмы позволяют существенно уменьшить время решения задачи нахождения собственных значений матриц.

В работе получены следующие теоретические и практические результаты:

1. Проведен анализ возможностей аппаратурной реализации алгоритмов нахождения собственных значений матриц, в результате которого установлено, что основной операцией при нахождении собственных значений матриц является выполнение псевдоунитарных преобразований.

2. Выделен набор типовых псевдоунитарных преобразований, используемых при нахождении собственных значений матриц.

3. Разработан класс ДЛП-алгоритмов нахождения собственных значений матриц модифицированным методом Якоби, методом гиперболических вращений и методом псевдоотражений.

4. Разработана методика исследования сходимости алгоритмов нахождения собственных значений матриц, основанная на геометрической интерпретации преобразования подобия.

5. Проведено сравнение количественных характеристик аппаратурных блоков, реализующих разработанные алгоритмы нахождения собственных значений матриц, согласно которому использование предложенных в работе алгоритмов позволяет, по сравнению с аппаратурной реализацией традиционных методов, в 4-8 раз уменьшить время решения задачи нахождения собственных значений матриц при уменьшении аппаратурных затрат в 2-6 раз.

Синтезированные алгоритмы были использованы при разработке схемы устройства для нахождения собственных значений матриц, на которое получен патент РФ на изобретение.

1. Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров: Учеб. пособие. М.: Высш. шк., 1994. - 544 с.

2. А. с. 734703 СССР, МКИ в 06 ¥ 15/20. Устройство для преобразования компонент тензора / Духнич Е. И. № 2571966/18-24; Заяв. 23.01.78; Опубл. 16.05.80, Бюл. № 18; Приоритет 15.05.80. - 5 с.

3. А. с. 741274 СССР, МКИ О 06 Б 15/34. Устройство для вычисления синусно-косинусных произведений / Духнич Е. И., Митраков В. А. -2571967/18-24; Заяв. 23.01.78; Опубл. 18.06.80, Бюл. № 22; Приоритет 15.06.80.-4 с.

4. А. с. 1142830 СССР, МКИ в 06 ¥ 7/544. Устройство для определения модуля трехмерного вектора / Духнич Е. И. 3592736/24-24; Заяв. 18.05.83; Опубл. 28.02.85, Бюл. №8.-5 с.

5. Байков В. Д., Смолов В. В. Аппаратурная реализация элементарных функций в ЦВМ. Л.: Изд-во Ленинградского ун-та, 1975. - 91с.

6. Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры. М.: Радио и связь, 1985. - 228 с.

7. Беклкмишев Д. В. Курс аналитической геометрии и линейной алгебры. -М.: Наука, 1971.-328 с.

8. Воеводин. В. В. Вычислительные основы линейной алгебры. М.: Наука, 1977.-303 с.

9. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984.-318 с.

10. Выжиковски Р., Каневский Ю. С., Лепеха В. Л. Параллельные структуры для решения симметричной проблемы собственных значений // Электронное моделирование. 1991. - № 4. - С. 37-43.

11. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. - 576 с.

12. Деревенсков С. О. Быстрый ДЛП-алгоритм многомерного вращения вектора / Волгоград, гос. техн. ун-т. Волгоград, 1995. - 4 с. - Деп. в ВИНИТИ № 2442.

13. Духнич Е. И. Алгоритмы быстрого преобразования Якоби для многопроцессорной реализации. // Микропроцессорные вычислительные структуры: Сб. Таганрог, 1989. - Вып. 11. - С. 64-66.

14. Духнич Е. И. Аппаратурно-ориентированные алгоритмы быстрого преобразования Хаусхолдера // Б8РА-98: Труды межд. конф. М., 1998. -С. 181-186.

15. Духнич Е. И. Два обобщенных алгоритма дискретных линейных преобразований // Многопроцессорные вычислительные структуры. -Таганрог, 1984. Вып. 6. - С. 9-11.

16. Духнич Е. И. Класс алгоритмов для реализации процедур линейной алгебры с помощью комплекта СБИС // Многопроцессорные вычислительные структуры. Таганрог, 1991. - Вып. 13(XXII). - С. 25-28.

17. Духнич Е. И. Класс аппаратурно-реализованных алгоритмов для построения проблемно-ориентированных процессоров с новой архитектурой // Computers-89. Bratislava, Chechoslovakia, 1989. - P. 42-47.

18. Духнич E. И. Об одном подходе к выполнению цифровых линейных преобразований // Кибернетика. 1981. - №5. - С. 97-98.

19. Духнич Е. И. Синтез класса алгоритмов и вычислительных структур для реализации дискретных линейных преобразований.: Дис. . д. т. н. -Таганрог, 1985. 306 с.

20. Духнич Е. И., Андреев А. Е. Алгоритм для аппаратурной реализации комплексного вращения // Тезисы докладов I межвузовской научно-практической конференции студентов и молодых ученых г. Волжского / ВПИ ВолгГТУ Волжский, 1995. - С. 107-109.

21. Духнич Е. И., Андреев Е. А. Модифицированный алгоритм дискретного линейного преобразования гиперболического вращения // Концептуальное проектирование в образовании, техники и технологии: Сб. науч. тр. / ВолгГТУ. Волгоград, 1997. - С. 39-42.

22. Духнич Е. И., Андреев А. Е., Стрельников О. И. Применение псевдоунитарных преобразований для нахождения собственных значений матриц // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. Волгоград, 2000. - С. 53-57.

23. Духнич Е. И., Деревенсков С. О. ДЛП-алгоритмы многомерных вращений для СБИС-реализации // Многопроцессорные вычислительные структуры: Междуведомственный тематический научный сборник / ТРТИ. Таганрог, 1995.-Вып. 15-16.-С. 25-27.

24. Духнич Е. И., Егунов В. А. Алгоритмы многомерных отражений, ориентированные на систолическую реализацию // Проектирование ЭВМ: Межвузовский сборник научных трудов / РГРА. Рязань, 1994. - С. 57-63.

25. Духнич Е. И., Егунов В. А. Расширение области сходимости процесса ДЛП-отражения / Волгоград, гос. техн. ун-т. Волгоград, 1995. - 7 с.-Деп. в ВИНИТИ №2529.

26. Духнич Е. И., Лукашева Г. Н., Серов А. А. Модифицированные алгоритмы дискретных линейных преобразований вращения // Многопроцессорные вычислительные структуры. Таганрог, 1990. - Вып.12 (XXI). - С. 37-38.

27. Духнич Е. И., Мурашов С. В. Два варианта алгоритмов для быстрой аппаратурной реализации линейного преобразования отражения // Проектирование ЭВМ: Межвуз. сб. научн. трудов. Рязань, 1992. - С. 4751.

28. Егунов В. А. Разработка и исследование аппаратурно-ориентированных алгоритмов быстрого преобразования Хаусхолдера: Дис. . к. т. н. -Волгоград, 1996. 199 с.

29. Каляев А. В., Духнич Е. И. Алгоритмы для аппаратурной реализации преобразования компонентов тензоров // Автоматика (Рига). 1977. - № 2. - С. 79-82.

30. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. -М.: Наука, 1978. 832 с.

31. Кун С. Матричные процессоры на СБИС: Пер. с англ. М.: Машиностроение, 1990. - 672 с.

32. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ.- М.: Мир, 1991. 367 с.

33. Параллельный алгоритм Волдера для операции поворота и его применение в машинной графике / Е. И. Артамонов, Ш.-М. А. Исмаилов, О. Г. Кокаев, В. Н. Хачумов // Управляющие системы и машины. 1990. -№ 1. - С. 106-109.

34. Парлетт Б. Симметричная проблема собственных значений. Численные методы. М.: Наука, 1983. - 384 с.

35. Пат. 1790787 РФ, МПК 5 G 06 F 15/347. Устройство для решения задач на собственные значения. / Р. Выжиковский, Ю. С. Каневский, В. JI. Лепеха, М. К. Клименко. № 4908183/24; Заявлено 06.02.91; Опубл. 23.01.93 // Изобретения. - 1993. - № 3. - С. 223.

36. Пат. 2007749 РФ, МПК 5 G 06 F 7/548. Устройство для преобразования координат / Духнич Е. И., Ивахно В. П., Серов А. А. 4924087/24; Заяв. 02.04.91; Опубл. 15.02.94, Бюл. № 3. - 6 с.

37. Пат. 2040039 РФ, МПК 6 G 06 F 7/544. Устройство для определения модуля трехмерного вектора / Духнич Е. И., Серов А. А. № 93005835/24; Заяв. 01.02.93; Опубл. 20.07.95, Бюл. № 20. - 5 с.

38. Пат. 2080650 РФ, МПК 6 G 06 F 7/544. Устройство для вычисления модуля m-мерного вектора / Духнич Е. И., Егунов В. А. № 95104370/09; Заявлено 01.03.95; Опубл. 27.05.97 //Изобретения. - 1997. -№ 15. - С. 183.

39. Пат. 2117987 РФ, МПК G 06 F 17/16. Устройство для вычисления собственных значений (п-п) матриц. / Якуш В. П., Смирнов В. А. № 93025204/09; Заявлено 28.04.93; Опубл. 20.08.98 // Изобретения. - 1998. -№23.-С 408-410.

40. Пат. 2125291 РФ, МПК G 06 F 17/14. Устройство для вычисления скользящего спектра / Духнич Е. И., Силантьев Г. В. № 98104872/09; Заявлено 24.02.98; Опубл. 20.01.99 // Изобретения. - 1999. - № 2. - С. 549550.

41. Пат. 2168760 РФ, МПК 7 G 06 F 17/16, 7/544. Устройство для вычисления собственных значений матриц / Духнич Е. И., Стрельников О. И. № 2000100287/09; Заяв. 05.01.2000; Опубл. 10.06.2001, Бюл. № 16 - 10 с.

42. Претт У. Цифровая обработка изображений. М: Наука, 1982.

43. Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ. / Под ред. С. Гуна, X. Уайтхауза, Т. Кайлата. М.: Радио и связь, 1989.-472 с.

44. Систолические структуры: Пер. с англ. / Под ред. У. Мура, Э. Маккейба, Р. Уркхарта. М.: Радио и связь, 1993. - 416 с.

45. Стрельников О. И. Аппаратурно-ориентированные алгоритмы нахождения собственных чисел действительных матриц // Региональная конференция студентов и молодых учёных: Тезисы докладов. Волгоград, 1996. - С. 8788.

46. Стрельников О. И. Синтез аппаратурно-ориентированных алгоритмов нахождения собственных чисел действительных матриц // Всероссийская научная конференция студентов и аспирантов: Тезисы докладов. -Таганрог, 1997.-С. 120-121.

47. Стренг Г. Линейная алгебра и ее применения: Пер. с англ. М.: Мир, 1980.-454 с.

48. Уилкинсон Д. X., Райнш К. Справочник алгоритмов на языке АЛГОЛ. М.: Машиностроение, 1976. 390 с.

49. Хорн Р., Джонсон Ч. Матричный анализ. М.: Наука, 1989. - 665 с.

50. Шевцов Г. С. Линейная алгебра: Учеб. пособие. М.: Гарданики, 1999. -360 с.

51. Шишкин Е. В. Линейные пространства и отображения. М.: Изд-во МГУ, 1987-311 с.

52. Ahmed Н.М., Delosme J.-M., Morf M. Highly Concurrent Computing Structures for Matrix Arithmetic and Signal Processing. // IEEE Computer. -1982.-Nl.-P. 65-82.

53. 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.

54. 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.

55. Cavallaro J. R., Luk F. T. CORDIC Arithmetic for an SVD Processor. // Journal of Parallel and Disributed Computing. 1988. -N5. - P. 271-290.

56. Configuring FLEX 1 OK Devices / Altera Corporation. 1998. - 25 P.

57. Doukhnitch E., Strelnikov O., Andreev A. Application of Kronecker Matrix Product for the Synthesis of Hardware-oriented DSP Algorithms // Digital

58. Signal Processing and its Applications DSPA-99. Moscow, 1999. - V. 1. - P. 281-282.

59. 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.

60. FLEXI OK Embedded Programmable Logic Device Family / Altera Corporation.- 1999.- 128 P.

61. Götze 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.

62. Hekstra G. J., Deprettere E. F. Floating-point CORDIC. // In Proceedings of the 11th Symposium on Computer Arithmetic / IEEE. 1993. - P. 130-137.

63. Hsiao S.-F. Multidimensional CORDIC Algorithms: Ph. D. Dissertation. 1993. -199 p.

64. Hsiao S.-F., Delosme J.-M. Householder CORDIC Algorithm. // IEEE Transactions on Computers. 1995. - Vol. 44(8). - P. 990-1001.

65. 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.

66. 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.

67. Muller J.-M. Discrete Basis and Computation of Elementary Functions // IEEE TRANSACTIONS ON COMPUTERS. 1985. - VOL. c-34, N9. - P. 857-862.

68. 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.