2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 разреженные матрицы
Сообщение18.12.2008, 18:11 


18/12/08
2
Товарищи профессионалы, посоветуйте пожалуйста литературу по разреженным матрицам! В основном интересуют схемы хранения и их анализ.
Нашёл книги: Тьюарсон - разреженные матрицы (перевод), Писсанецки - технология р.м. (перевод), Дж. Лю - численное решение больших разреженных систем уравнений (перевод).
Эти книги 70-х - 80-х годов, может есть прогресс в этой области и книги поновее? подскажите пожалуйста!
Буду очень благодарен, если подскажите где взять электронные книги по сабжу.

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


23/12/05
12046
http://www.cise.ufl.edu/research/sparse/

http://www.mathworks.com/access/helpdesk/help/pdf_doc/otherdocs/simax.pdf

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


19/07/08
1266
Зависит от того, что вы хотите с этими матрицами делать. Если только хранить, то вот стандарты:
http://www.netlib.org/linalg/html_templates/node90.html
Там есть ссылка например на Саада -- думаю, стоит читать именно его, поскольку на него все ссылаются когда речь заходит о разреженных матрицах. Что касается именно хранения думаю с начала 90-х ничего кардинально нового не сделали.

 Профиль  
                  
 
 
Сообщение19.12.2008, 20:06 


18/12/08
2
Спасибо photon и nestoklon! В приведённых Вами документах довольно обширная библиография по теме (я пока всё не просмотрел). Меня кроме схем хранения интересует их сравнительный анализ, особенно при работе с внешней памятью (очень большие системы). Может что подскажете? Спасибо.

 Профиль  
                  
 
 
Сообщение20.02.2009, 20:06 


20/02/09
11
Tyumen
Есть три вопроса по-поводу разреженных матриц.

1) Не могли бы Вы дать ссылки или описать в общих чертах, что собой представляет John Appleyard Linear Solver (JALS).

2) Посоветуйте, какой метод реализовать для решения систем уравнений с блочно-трёхдиагональной (пятидиагональной) матрицей для ~10000 неизвестных.

3) Какое приемлемое время решения таких систем на современном персональном компьютере, к чему я должен стремиться. Методом исключения Гаусса решение получается за 22 минуты, что для меня не подходит. Я понимаю, что время зависит от железа, мне хотелось бы знать порядок величины.

 Профиль  
                  
 
 
Сообщение24.02.2009, 03:00 
Аватара пользователя


23/02/09
259
я писала алгоритм правда то были не неразреженные матрицы а вполне нормальные квдратные -полностью заполненые -мой домашний компутер тянул максимально 1024\times 1024 на большее не хватало памяти:( -так вот у меня на решение уходило 15 сек примерно -правда я не оптимизировала там ни чего особенно -мне этого хватило на курсовую:) :roll:
а что методом Гауса до сих пор пользуються?(имею ввиду на РС)? :roll:

 Профиль  
                  
 
 
Сообщение24.02.2009, 03:46 
Заблокирован
Аватара пользователя


13/01/09

335
karakurt2 писал(а):
Есть три вопроса по-поводу разреженных матриц.

1) Не могли бы Вы дать ссылки или описать в общих чертах, что собой представляет John Appleyard Linear Solver (JALS).

2) Посоветуйте, какой метод реализовать для решения систем уравнений с блочно-трёхдиагональной (пятидиагональной) матрицей для ~10000 неизвестных.

3) Какое приемлемое время решения таких систем на современном персональном компьютере, к чему я должен стремиться. Методом исключения Гаусса решение получается за 22 минуты, что для меня не подходит. Я понимаю, что время зависит от железа, мне хотелось бы знать порядок величины.

По поводу 2 пункта: если система не имеет специфической структуры (например, построена на дереве и тогда решение получается мгновенно), то 10000 неизвестных для современного компа - это семечки и систему лучше решать, как плотную, используя при этом эффективные библиотеки. Дело в том, что при решении систем уравнений современными методами львиную долю забирает умножение матриц, а самому написать эффективную процедуру умножения матриц даже для очень продвинутого пользователя - это непосильная задача. Советую при этом использовать ось с x64, т.к. можно поставить больше оперативной памяти и, кроме того, профессиональные алгоритмы умножения матриц под x64 работают быстрей, чем на x86.
По поводу 3 пункта: на 4-ядерном проце 22 минуты можно сократить не менее, чем в 10 раз.
Но все эти замечания относятся к матрицам произвольной структуры. В вашем случае ленточной м-цы советую использовать библиотеку Intel MKL (под Linux бесплатна), в ней используются алгоритмы, восходящие еще ко временам Уилкинсона - ничего принципиально нового здесь с тех времен не придумано, за исключеннием некоторых мелких технических деталей. Исходные тексты можно взять из свободно распространяемого пакета Lapack, который обновлялся совсем недавно. Эти алгоритмы разработаны с участием довольно известных американских математиков. Но лучше использовать не исходные тексты, а библиотеку Intel MKL.

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


15/05/05
3445
USA
karakurt2 писал(а):
2) Посоветуйте, какой метод реализовать для решения систем уравнений с блочно-трёхдиагональной (пятидиагональной) матрицей для ~10000 неизвестных.

Метод прогонки для такого типа матриц описан здесь:
Самарский А. А,, Николаев Е. С. Методы решения сеточных уравнений. М. Наука. 1978.
Метод быстрый, хотя не всегда устойчивый. Алгоритм простой, легко программируется.

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


19/07/08
1266
karakurt2 в сообщении #188130 писал(а):
для решения систем уравнений с блочно-трёхдиагональной (пятидиагональной) матрицей

Ленточные матрицы есть в Lapack. Ничего лучше самому написать не получится. Если вам категорически не нравится фортран и вы не умеете вызывать фортран из других языков, там на странице по ссылке внизу есть варианты на си и яве, интерфейсы для 95 фортрана и c++.
Время решения для ленточной матрицы 1000х1000 будет исчезающе мало. Доли секунды.

 Профиль  
                  
 
 
Сообщение24.02.2009, 10:26 
Аватара пользователя


23/02/09
259
Yuri Gendelman в сообщении #189096 писал(а):
Самарский А. А,, Николаев Е. С. Методы решения сеточных уравнений. М. Наука. 1978.

Слишком старая книжка :roll: лучше воспользуйтесь чем по современее вы просто не представляете себе сколько новых и эфективных алгоритмов найдено за последние 5-10 лет:) :roll:

 Профиль  
                  
 
 
Сообщение24.02.2009, 13:12 
Заблокирован
Аватара пользователя


13/01/09

335
Лиля писал(а):
вы просто не представляете себе сколько новых и эфективных алгоритмов найдено за последние 5-10 лет:)

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

 Профиль  
                  
 
 
Сообщение24.02.2009, 20:47 
Аватара пользователя


23/02/09
259
Nik_Svan в сообщении #189175 писал(а):
Со времен Уилкинсона принципиально нового для решения систем линейных уравнений с ленточными матрицами ничего не придумали

ну да конечно... а оно нужно? современные алгоритмы позволяют решать обычные системы линейных уровнений очень быстро.... а в некоторых алгритмах требуеться разбиение матрицы на 3 матрицы 1-ая с нижним заполненым триугольником 2-ая с верхним а 3-яя...... как раз ленточная.... :roll: -ток это не будет очевидным если вы не увидите вывода этих алгоритмов

 Профиль  
                  
 
 
Сообщение24.02.2009, 21:20 
Заблокирован
Аватара пользователя


13/01/09

335
Лиля писал(а):
[ну да конечно... а оно нужно?

Лиля, вы излагаете очень интересные факты. Если не секрет, какое у вас образование?

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


15/05/05
3445
USA
Лиля писал(а):
Слишком старая книжка: лучше воспользуйтесь чем по современее вы просто не представляете себе сколько новых и эфективных алгоритмов найдено за последние 5-10 лет
Это, возможно, относится к матрицам более общего вида. Метод прогонки для 3-5 диагоналей имеет сложность порядка $O(n)$. Врял ли его можно принципиально улучшить.

 Профиль  
                  
 
 
Сообщение21.03.2009, 02:39 


26/11/06
76
Если речь идет о симметричных разреженных матрицах то на данный момент это Sparse Direct Solver - ы (тонко учитывающие портрет матрицы) + мультиуровневые алгоритмы разбияния графов а также мульфронтальные методы - это из прямых! Если же матрица ещё и положительноопределенна - то тут есть одно мощное средство - это CG+Высококачественные устойчивые предобуславливатели + те же самые мультиуровневые алгоритмы разбиения графов. Такие алгоритмы сейчас позволяют решать системы >1 млн. уравнений на обычных персональных компьютерах.

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

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



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

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


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

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