Роль "железа" в разработке новых численных алгорит

[abc_qmost]

Существует свободно распространяемый пакет по линейной алгебре LAPACK, который также
включает и реализацию базовых алгоритмов линейной алгебры BLAS. За его разработкой стоят известные алгоритмисты и математики (например, автор книги "Вычислительная
линейная алгебра (теория и приложения)" Дж. Деммель). Этот пакет находится в постоянном
развитии (последняя версия вышла в феврале этого года) и включает в себя ряд новых
алгоритмов, которые появились в конце прошлого века.
Существует и крайне эффективная реализация этого пакета - Intel MKL.
В начале 80-х годов, занимаясь реализацей алгоритмов по полуэмпирическим расчетам, я
столкнулся как с нехваткой оперативной памяти при расчете больших систем. так и с довольно медленными алгоритмами диагонализации, которая "жрет" львиную долю расчетного времени (узким звеном была работа с трехдиагональной матрицей).Тогда и был мною разработан новый (неопубликованный) алгоритм, снявший проблему по обработке трехдиагональных матриц. Результатом работы была публикация (см. статью [1] ], опубликованную на моей странице ‹…› (ссылка удалена — нг), в части, посвященной процессору P4).
В начале этого века, по разным причинам, пришлось вернуться к алгебраической проблеме
собственных значений. Стартовая точка определялась как моими разработками 80-х годов,
так и замечательным пакетом LAPACK. Критерием эффективности стало сравнение с пакетом
Intel MKL. Были достигнуты следующие результаты (с анализом роли "железа"):
1. Найден новый подход к решению алгебраической проблемы собственных значений
и собственных векторов для трехдиагональных матриц, который позволил увеличить
скорость и привел к значительной экономии оперативной памяти.
Для эффективной работы этого алгоритма необходима поддержка "железом" IEEE-арифметики.
2. Разработан новый алгоритм матричного умножения, который позволил увеличить
скорость перехода от матрицы собственных векторов трехдиагональной матрицы
к матрице собственных векторов исходной матрицы.
Основную роль в разработке этого алгоритма сыграл численный эксперимент.
3. Модифицирован алгоритм Pal-Walker-Kahan'а, который позволил увеличить скорость
нахождения собственных значений трехдиагональной матрицы в несколько раз в случае
медленной сходимости.
Эта модификация связана с отличием ортогональных и неортогональных преобразований.
4. Применены блочные методы к упакованным матрицам, что привело к увеличению скорости
трехдиагонализации почти в 3 раза и к увеличению скорости перехода от матрицы
собственных векторов трехдиагональной матрицы к матрице собственных векторов
исходной матрицы в 8 раз.
Здесь "мозгов" много не надо. Необходимо хорошо попотеть.
5. Усовершенствованная реализация базовых алгоритмов линейной алгебры позволила
увеличить скорость BLAS2 (IA32 и EM64T) и BLAS3 (IA32).
Здесь основную роль сыграл численный эксперимент. Хотелось бы отметить радикальное
отличие реализации алгоритмов для IA32 и EM64T.
С новыми результатами можно ознакомиться в статьях [9, 10, 11], опубликованных на моей странице ‹…› (ссылка удалена — нг), в части, посвященной процессору P4.

[vasionok]

всё это очень интересно, особенно то, что у вас получилось ускорить алгоритм PWK аж до трёх раз. Так же вы обставили BLAS в Intel MKL, что сильно, но не столь удивительно --- приходилось слышать, что GotoBLAS тоже быстрее MKL. Не совсем понял что значит "новый алгоритм векторного умножения", п. 3.1. Умножение матрицы на вектор или вектора на вектор? Или это умножение матриц, векторизованное с использованием SSE? Глюки метода Relatively Robust Representations вроде пофиксили, не уверен что это успело попасть в MKL.

по ссылкам данным в конце страницы я нашёл статьи по квантовой химии, но где же описание алгоритмов?

[abc_qmost]

vasionok писал(а):

всё это очень интересно, особенно то, что у вас получилось ускорить алгоритм PWK аж до трёх раз.

Такой разрыв достигается на медленно сходящихся задачах.

vasionok писал(а):

...приходилось слышать, что GotoBLAS тоже быстрее MKL...

За последние годы Intel MKL вышел на результаты, которые не уступают лучшим мировым пакетам.
Что касается GotoBLAS, то о его скорости можно судить из сравнения скоростей моей версии GAMESS и PC GAMESS, в которой используется GotoBLAS (сравнение приведено на моей странице).

vasionok писал(а):

Не совсем понял что значит "новый алгоритм векторного умножения"...

Этот мой пассаж я не хочу комментировать. Слишком большой кровью мне дался этот результат.

vasionok писал(а):

Глюки метода Relatively Robust Representations вроде пофиксили, не уверен что это успело попасть в MKL.

Intel MKL и авторы LAPACK довольно сильно завязаны друг с другом. Все изменения уже отражены. Мои результаты, посвященные RRR методу, устарели. Ошибки вышли на более тонкий уровень.

vasionok писал(а):

по ссылкам данным в конце страницы я нашёл статьи по квантовой химии, но где же описание алгоритмов?

Эти статьи, опубликованные на моей странице, являются подтверждением дееспособности моей диагонализации. Что касается описания алгоритмов, то их разработку и реализацию я вел в свободное от работы время в порядке личной инициативы. Я вел переговоры с главным менеджером Intel MKL (он математик и его диссертация посвящена диагонализации), но к общему знаменателю прийти не удалось.

[Zai]

abc_qmost писал(а):

Я вел переговоры с главным менеджером Intel MKL

Насколько я понимаю Вы где-то являетесь конкурентом разработок Intel MKL. Сам проект Intel MKL не является основным направление Intel и вполне возможно, что он является единственным сотрудником Intel по этому направлению без значительной финансовой свободы в заключении новых контрактов со сторонними организациями или частными лицами. Intel несколько не свободна в выборе внешних организаций и полагается по всей видимости на ведущие американские университеты.

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

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

[нг]

Вопросы — в ЛС

[нг]

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

Темы закрыты. Ссылки удалены.