linpack

[abc_qmost]

Oam писал(а):

abc_qmost писал(а):

Если оставить в стороне блочные методы, которые не имеет смысла применять для малых матриц, то сильно изменилась tql2, вернее та ее часть, которая отвечает за работу с трехдиагональной матрицей (и то недавно). Скорость этой части в некоторых случаях возрасла на 500%. Этот алгоритм реализован в пакете Intel MKL.

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

Посмотрите мой ответ Юрию Гендельману. Я думаю, что это то, что Вам нужно.

[Oam]

abc_qmost писал(а):

Посмотрите мой ответ Юрию Гендельману. Я думаю, что это то, что Вам нужно.

К сожалению ваша ссылка
http://www.cs.utk.edu/~ghenry/thesis.ps
не читабельна:

Цитата:

Forbidden
You don't have permission to access /~ghenry/thesis.ps on this server.
Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.

403-я ошибка это не плохой интернет, а запрещенный доступ к странице для "недостойных".

Насколько я понял из сопроводительного текста, в MKL этот алгоритм еще не вошел. А, значит, надежда его применить становится совсем мизерной.

[abc_qmost]

Oam писал(а):

abc_qmost писал(а):

Посмотрите мой ответ Юрию Гендельману. Я думаю, что это то, что Вам нужно.

К сожалению ваша ссылка
http://www.cs.utk.edu/~ghenry/thesis.ps
не читабельна:

Цитата:

Forbidden
You don't have permission to access /~ghenry/thesis.ps on this server.
Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.

403-я ошибка это не плохой интернет, а запрещенный доступ к странице для "недостойных".

Насколько я понял из сопроводительного текста, в MKL этот алгоритм еще не вошел. А, значит, надежда его применить становится совсем мизерной.

Процитированное письмо относится к концу 2004 года. И по тому ускорению, которое получила программа, новый алгоритм вошел в новые версии Intel MKL. Раньше thesis.ps загружался без проблем. Но даже с этим ускорением он меня не интересовал, т.к. он все-равно медленный. Поэтому я его не сохранил (во всяком случае, поиск не дал положительных результатов). Я думаю, что Вам имеет смысл обратиться к Юрию Гендельману. Он живет в Америке и для него достать эту штуку - не проблема.

[abc_qmost]

Oam писал(а):

abc_qmost писал(а):

Посмотрите мой ответ Юрию Гендельману. Я думаю, что это то, что Вам нужно.

К сожалению ваша ссылка
http://www.cs.utk.edu/~ghenry/thesis.ps
не читабельна:

Цитата:

Forbidden
You don't have permission to access /~ghenry/thesis.ps on this server.
Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.

403-я ошибка это не плохой интернет, а запрещенный доступ к странице для "недостойных".

Насколько я понял из сопроводительного текста, в MKL этот алгоритм еще не вошел. А, значит, надежда его применить становится совсем мизерной.

Файл нашелся. Как Вам его переправить?

Добавлено спустя 2 минуты 52 секунды:

Re: linpack

Yuri Gendelman писал(а):

abc_qmost писал(а):

Алгоритм для алгебраической проблемы с.з. и с..в. симметричной трехдиагональной м-цы в последних версиях Intel MKL изменен.

А что именно изменено, математика или реализация? Если математика, то нет ли у Вас ссылок на детали?

Файл нашелся. Как Вам его переправить?

[Yuri Gendelman]

abc_qmost писал(а):

Я думаю, что Вам имеет смысл обратиться к Юрию Гендельману. Он живет в Америке и для него достать эту штуку - не проблема.

Мне понравилась Ваша шутка

abc_qmost писал(а):

Файл нашелся. Как Вам его переправить?

Спасибо. Я Вам ответил в ЛП.

Для поиска статей, отчетов и т.п. я могу посоветовать сайт http://citeseer.ist.psu.edu/.
Правда диссертации Грега Генри я там не нашел. Но его статьи по параллельным алгоритмам есть.

[KSergP]

увадаемый abc_qmost, а вы где и кем работаете?

[нг]

KSergP
Подобные вопросы уместнее задавать в ЛС.

[vasionok]

Oam писал(а):

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

я думаю уважаемый abc_qmost имеет в виду библиотеку LAPACK (произносится "эл-эй-пэк"), которая присутствует в Intel MKL. Эта библиотека разрабатывается широким научным коллективом, и свободно распространяется на том же сайте, что и LINPACK и EISPACK --- http://www.netlib.org/, точнее http://www.netlib.org/lapack/. Вот отдельные ссылки на код интересующих вас процедур:

http://www.netlib.org/lapack/explore-html/dsytrd.f.html --- приведение действительной симметричной матрицы к трёхдиагональному виду ортогональными преобразованиями подобия

http://www.netlib.org/lapack/explore-html/dsteqr.f.html --- нахождение собственных значений и векторов трёхдиагональной матрицы методом QR (или QL)
http://www.netlib.org/lapack/explore-html/dsterf.f.html --- QL и QR алгоритмы в форме Pal-Walker-Kahan. Чуть быстрее, но только для собственных значений
http://www.netlib.org/lapack/explore-html/dstebz.f.html --- метод деления пополам для собственных значений
http://www.netlib.org/lapack/explore-html/dstein.f.html --- метод обратных итераций для собственных векторов
http://www.netlib.org/lapack/explore-html/dstedc.f.html --- метод divide and conquer
http://www.netlib.org/lapack/explore-html/dstegr.f.html --- метод на основе relatively robust representations

http://www.netlib.org/lapack/explore-html/dsyev.f.html --- решение задачи для плотной симметричной матрицы на основе перечисленных выше процедур.

Производители процессоров часто выпускают версию библиотеки LAPACK подогнанную под собственные процессора, примерами являются Intel MKL и AMD ACML. К примеру, они выбирают оптимальные размеры блоков в блочных алгоритмах, и компилируют код своим компилятором с оптимально выбранными ключами. Так же они могут модифицировать и сам алгоритм, чтобы он лучше ложился на архитектурные (например, векторные) особенности процессора. Но, я думаю, будь эти изменения принципиальными, они были бы произведены на уровне LAPACK, а не конкретной компиляции. Могу ошибаться.

Некоторые из алгоритмов LAPACK являются улучшенными версиями аналогичных процедур в LINPACK / EISPACK. Улучшения касаются не только скорости, но и надёжности. Под рукой нет ссылки, но могу, например, указать статью расказывающую про подобные улучшения в алгоритме деления пополам.

[abc_qmost]

vasionok писал(а):

я думаю уважаемый abc_qmost имеет в виду библиотеку LAPACK ...

Насколько я знаю, Oam разобрался со своими проблемами.

[Freude]

Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?

[abc_qmost]

Freude писал(а):

Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?

для скорости

[Yuri Gendelman]

Freude писал(а):

Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?

Это - пример модульности разработки. Никто не мешает пользователю написать свою подпрограмму из двух строчек, с двумя вызовами.
Если Вы имеете в виду почему нет единого алгоритма, то просто потому, что не придумали такого.
Для решения СЛУ тоже используют два этапа - LU-разожение и затем прогонку. Этот вариант эффективнее, чем метод Гаусса.

[Freude]

Спасибо, теперь понятно

[abc_qmost]

Yuri Gendelman писал(а):

Freude писал(а):

Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?

Это - пример модульности разработки. Никто не мешает пользователю написать свою подпрограмму из двух строчек, с двумя вызовами.
Если Вы имеете в виду почему нет единого алгоритма, то просто потому, что не придумали такого.
Для решения СЛУ тоже используют два этапа - LU-разожение и затем прогонку. Этот вариант эффективнее, чем метод Гаусса.

Dear Yuri,

Когда я отвечал Freude'у: "для скорости", то имел ввиду несколько иное: существует одно subroutine для диагонализации, а именно реализация метода Якоби (1846 год). Но этот метод очень медленный, хотя у него есть свои преимущества. Остальную часть ответа я считал очевидной.

Best regards,
Yurii Sigolaev

[Yuri Gendelman]

abc_qmost писал(а):

Остальную часть ответа я считал очевидной.

Я постарался расписать очевидную часть ответа. Кроме того, метод Якоби предназначен только для симметрических матриц.
Во времена, "когда компьютеры были большими, но с маленькой памятью", метод Якоби иногда применялся в модифицированной форме (барьерный МЯ, или МЯ с преградами). Получалось немного быстрее и почти так же компактно.