2014 dxdy logo

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

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




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

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

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

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

 
 
 
 Re: Трехдиагонализация матрицы
Сообщение12.03.2011, 21:11 
А Вам не поможет книга в нашей библиотеке

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

?

 
 
 
 Re: Трехдиагонализация матрицы
Сообщение13.03.2011, 11:24 
Можете посмотреть так-же книгу из нашей библиотеки:

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

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

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

 
 
 
 
Сообщение13.03.2011, 19:04 
Я немного попонятнее распишу что сейчас есть.
Я строю гамильтониан. Далее я его превращаю в трехдиагональную матрицу вида:
$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 ] 


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