2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение27.08.2007, 18:28 


05/08/07

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

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

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

 Профиль  
                  
 
 
Сообщение27.08.2007, 18:54 


30/10/06
33
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 


05/08/07

194
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 


05/08/07

194
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 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: linpack
Сообщение01.10.2007, 11:44 


15/11/05
46
Томск
увадаемый abc_qmost, а вы где и кем работаете?

 Профиль  
                  
 
 
Сообщение01.10.2007, 23:59 
Экс-модератор
Аватара пользователя


30/11/06
1265
 !  KSergP
Подобные вопросы уместнее задавать в ЛС. :offtopic3:

 Профиль  
                  
 
 
Сообщение23.10.2007, 11:02 


23/10/07
10
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 


05/08/07

194
vasionok писал(а):
я думаю уважаемый abc_qmost имеет в виду библиотеку LAPACK ...

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

 Профиль  
                  
 
 
Сообщение16.11.2007, 13:43 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение16.11.2007, 17:05 


05/08/07

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

для скорости

 Профиль  
                  
 
 
Сообщение16.11.2007, 19:49 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение17.11.2007, 13:42 
Заслуженный участник
Аватара пользователя


20/01/06
1037
Спасибо, теперь понятно

 Профиль  
                  
 
 
Сообщение18.11.2007, 11:08 


05/08/07

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

Dear Yuri,

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

Best regards,
Yurii Sigolaev

 Профиль  
                  
 
 
Сообщение18.11.2007, 15:41 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group