2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение27.08.2007, 18:28 
Oam писал(а):
abc_qmost писал(а):
Если оставить в стороне блочные методы, которые не имеет смысла применять для малых матриц, то сильно изменилась tql2, вернее та ее часть, которая отвечает за работу с трехдиагональной матрицей (и то недавно). Скорость этой части в некоторых случаях возрасла на 500%. Этот алгоритм реализован в пакете Intel MKL.

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

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

 
 
 
 
Сообщение27.08.2007, 18:54 
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 этот алгоритм еще не вошел. А, значит, надежда его применить становится совсем мизерной.

 
 
 
 
Сообщение27.08.2007, 19:47 
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 загружался без проблем. Но даже с этим ускорением он меня не интересовал, т.к. он все-равно медленный. Поэтому я его не сохранил (во всяком случае, поиск не дал положительных результатов). Я думаю, что Вам имеет смысл обратиться к Юрию Гендельману. Он живет в Америке и для него достать эту штуку - не проблема.

 
 
 
 
Сообщение27.08.2007, 23:11 
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 изменен.
А что именно изменено, математика или реализация? Если математика, то нет ли у Вас ссылок на детали?

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

 
 
 
 
Сообщение28.08.2007, 00:41 
abc_qmost писал(а):
Я думаю, что Вам имеет смысл обратиться к Юрию Гендельману. Он живет в Америке и для него достать эту штуку - не проблема.
Мне понравилась Ваша шутка :D

abc_qmost писал(а):
Файл нашелся. Как Вам его переправить?
Спасибо. Я Вам ответил в ЛП.

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

 
 
 
 Re: linpack
Сообщение01.10.2007, 11:44 
увадаемый abc_qmost, а вы где и кем работаете?

 
 
 
 
Сообщение01.10.2007, 23:59 
Аватара пользователя
 !  KSergP
Подобные вопросы уместнее задавать в ЛС. :offtopic3:

 
 
 
 
Сообщение23.10.2007, 11:02 
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. Улучшения касаются не только скорости, но и надёжности. Под рукой нет ссылки, но могу, например, указать статью расказывающую про подобные улучшения в алгоритме деления пополам.

 
 
 
 
Сообщение24.10.2007, 13:02 
vasionok писал(а):
я думаю уважаемый abc_qmost имеет в виду библиотеку LAPACK ...

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

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

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

для скорости

 
 
 
 
Сообщение16.11.2007, 19:49 
Freude писал(а):
Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?
Это - пример модульности разработки. Никто не мешает пользователю написать свою подпрограмму из двух строчек, с двумя вызовами.
Если Вы имеете в виду почему нет единого алгоритма, то просто потому, что не придумали такого.
Для решения СЛУ тоже используют два этапа - LU-разожение и затем прогонку. Этот вариант эффективнее, чем метод Гаусса.

 
 
 
 
Сообщение17.11.2007, 13:42 
Аватара пользователя
Спасибо, теперь понятно

 
 
 
 
Сообщение18.11.2007, 11:08 
Yuri Gendelman писал(а):
Freude писал(а):
Объясните мне, пожалуйста, почему в Intel MKL и LAPACK для отыскания собственных значений и собственных векторов матрицы надо использовать две операции - вначале привести матрицу к трехдиагональному виду, а затем диагонализировать. Почему это не реализовано в одном subroutine?
Это - пример модульности разработки. Никто не мешает пользователю написать свою подпрограмму из двух строчек, с двумя вызовами.
Если Вы имеете в виду почему нет единого алгоритма, то просто потому, что не придумали такого.
Для решения СЛУ тоже используют два этапа - LU-разожение и затем прогонку. Этот вариант эффективнее, чем метод Гаусса.

Dear Yuri,

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

Best regards,
Yurii Sigolaev

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

 
 
 [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group