2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Трехдиагонализация матрицы
Сообщение11.03.2011, 04:43 


11/03/11
3
Добрый день, форумчане,
В данный момент я занимаюсь подсчетом количества частиц на узлах в модели Андерсона.
Соотвественно я строю гамильтониан, в котором я указываю энергии состояние электоронов на узлах и "вероятность" перехода из одного состояния в другое. Поэтому матрица Гамильтониана получается жутко большой и работать в сыром виде с ней сложно. Удобнее с ней работать в трехдиагональном виде.
Так вот проблема в том, как получить трехдиагональную матрицу из произвольной?
В методе рекурсий, который я нашел, все, соотвевенно, проводится прямой рекурсией, и учитывая размеры матрицы получается это долго :( Была идея каким-то образом распараллелить эти вычисления, но так как там не ветвлящаяся рекурсия я понятия не имею как.
Может кто сталкивался с подобной проблемой?
В инете поныткался на "A Parallel, Object-Oriented Implementation of the Dynamic Recursion Method", но ни примеров, ни кодов, ни самой статьи я найти не смог.

 Профиль  
                  
 
 Re: Трехдиагонализация матрицы
Сообщение11.03.2011, 15:25 
Заслуженный участник


15/05/05
3445
USA
Xenon в сообщении #421690 писал(а):
Соотвественно я строю гамильтониан, в котором я указываю энергии состояние электоронов на узлах и "вероятность" перехода из одного состояния в другое. Поэтому матрица Гамильтониана получается жутко большой и работать в сыром виде с ней сложно. Удобнее с ней работать в трехдиагональном виде.
Вопрос сформулирован не очень четко.
Что значит "удобнее с ней работать в трехдиагональном виде"?
По-моему еще удобнее с ней работать в (одно)диагональном виде. При этом на диагонали будут энергии состояний, а матрица преобразования - это собственные векторы. А вся задача в целом - нахождение собственных значений и собственных векторов симметричной (поскольку гамильтониан) матрицы.
Полистайте учебники по численным методам линейной алгебры.

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


11/03/08
9632
Москва
Ну, вообще-то привести матрицу общего вида к трёхдиагональной можно за конечное число шагов, а трёхдиагональную к диагональной - за в принципе бесконечное (хотя обрывают при достижении нужной точности). Видимо, это имеется в виду.
Приведение к трёхдиагональной - обычно первый шаг при вычислении С.З. QR-алгоритмом. Там и надо, видимо, копать.

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


11/03/11
3
Да, Евгений, вы в принципе правы.
По известной функции Грина я нахожу плотность состояний и соотвественно числа заполнения электронных состояний с каждой из проекций спина.
А матричный элемент элемент фунции Грина выражается в виде цепной дроби, которую приходиться рвать.
В исходном Гамильтониане на диагонали стоят энергии электронов Ei, a недиагональные матричные элементы Vij отличны от нуля в случае если узлы i и j являются ближайшими соседями.
И вопрос пока в том, как быстрее провести триагонализацию, и, самое главное - не только быстрее но и мультипоточно, чтобы иметь возможность разнести вычисления на разные сервера.
Тот алгоритм, что используется сейчас - рекурсивен. Мы фиксируем первый базисный вектор - например в i-ую координату ставим 1, а остальные забиваем 0, а дальше действуем H на наш новый базис и выражаем соотвественно рекурсивно элементы трехдиагональной матрицы. И "разбить" эту рекурсию на параллельно вычислимые подзадачи я чего-то ума не приложу как. Поэтому и спрашиваю совета.

 Профиль  
                  
 
 Re: Трехдиагонализация матрицы
Сообщение12.03.2011, 21:11 


03/09/05
217
Bulgaria
А Вам не поможет книга в нашей библиотеке

Уилкинсон Дж., Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра

?

 Профиль  
                  
 
 Re: Трехдиагонализация матрицы
Сообщение13.03.2011, 11:24 


03/09/05
217
Bulgaria
Можете посмотреть так-же книгу из нашей библиотеки:

Ортега Д. Введение в параллельные и векторные методы решения линейных систем

(http://lib.mexmat.ru/books/24902)

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


19/07/08
1266
Тоже очень похожую задачу время от времени пытаюсь решить получше чем то, что у меня сейчас есть. Сейчас есть ARPACK, которому для того чтобы он сходился надо делать shift-inverse transform, что весьма затратно или по скорости или по памяти так как даже решать разреженные матрицы можно массой способов, хорошего среди которых нет.
Vassil в сообщении #422351 писал(а):
Ортега Д. Введение в параллельные и векторные методы решения линейных систем
А поновее чего-нибудь не знаете? А то там кончается на сопряжённых градиентах, а с тех пор всё же некоторый прогресс наблюдался.

 Профиль  
                  
 
 
Сообщение13.03.2011, 19:04 


11/03/11
3
Я немного попонятнее распишу что сейчас есть.
Я строю гамильтониан. Далее я его превращаю в трехдиагональную матрицу вида:
$H=\left(\begin{array}{cccccc}
a_{1} & b_{1} & . & . & . & 0\\
b_{1} & a_{2} & b_{2} & . & . & .\\
. & b_{2} & a_{3} & b_{3} & . & .\\
. & . & b_{3} & . & . & .\\
. & . & . & . & . & .\\
0 & . & . & . & . & .\end{array}\right)$

Где коэффициенты элементы я считаю таким образом:
Я фиксирую первый базисный вектор - в нем i-ая кордината равна 1.
y1 = $\left(\begin{array}{c}
0\\
0\\
1\\
.\\
0\end{array}\right)$

Затем:
H | y$_{1}$ = a$_{1}$| y$_{1}${]} + b$_{1}$| y$_{2}]$

a$_{1}=${[} y$_{1}$| H | y$_{1}]$ , b$_{1}=$|| H | y$_{1}${]}
- a$_{1}${]} - a$_{1}|$ y$_{1}]$||

| y$_{2}${]} = $\frac{H|y_{1}]-a_{1}|y_{1}]}{b_{1}}$

\textcyr{\char232} \textcyr{\char242}.\textcyr{\char228}.

H | y$_{n}${]} = b$_{n-1}|$y$_{n-1}]$+ a$_{n}|$ y$_{n}]$+ b$_{n}$|
y$_{n+1}]$

b$_{n}$= || H | y$_{n}]$ - b$_{n-1}|$ y$_{n-1}${]} - a$_{n}|$
y$_{n}${]} ||

| y$_{n+1}]=\frac{H|y_{n}]-b_{n-1}|y_{n-1}]-a_{n}|y_{n}]}{b_{n}}|$
Фиксированностью i-го я пользуюсь когда вычисляю матричные элементы функции грина, потому что в таком базисе
G$_{ii}=[$ y$_{1}|$G|y$_{1}]$
Именно его я использую для подсчета количества частиц со спином вверх на i-ом узле (для подсчет элементов со спином вниз беру i+1)
И вот задача тогда, скорее как быстрее трехдиагонализировать матрицу с фиксированным первым базисным вектором.
Используя эту матрицу я выписываю ряд уравнений и представляю G$_{ii} в виде цепной дроби, которая заканчивается на b$_{n-1}$ члене, либо обрывается при первом нулевом b$_{n}$, потому что все остальные члены зануляются. То есть операцию можно прекращать раньше.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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