Как реализовать вычисление собственных значений с помощью MapReduce/Hadoop?

Ответ 1

PageRank решает проблему доминантного собственного вектора, итеративно находя установившееся состояние дискретного потока сети.

Если NxM-матрица A описывает вес связи (количество потока) от node n до node m, то

p_{n+1} = A . p_{n} 

В пределе, когда p сходится к установившемуся состоянию (p_n + 1 = p_n), это задача собственного вектора с собственным значением 1.

Алгоритм PageRank не требует, чтобы матрица сохранялась в памяти, но неэффективна для плотных (не разреженных) матриц. Для плотных матриц MapReduce является неправильным решением - вам нужна локальность и широкий обмен между узлами - и вам следует вместо этого взглянуть на LaPACK и MPI и друзей.

Вы можете увидеть рабочую реализацию pagerank в библиотеке wukong (потоковая передача для рубинов) или в Подструктура Heretrix pagerank. (Код irctrix выполняется независимо от Heretrix)

(отказ от ответственности: я автор wukong.)

Ответ 2

Преамбула:

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

Возьмем, например, следующий цикл:

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        m[i][j]++; 
    }
}

И учитывая матрицу следующего макета:

       j=0   j=1   j=2
 i=0  [   ] [   ] [   ]
 i=1  [   ] [   ] [   ]
 i=2  [   ] [   ] [   ]

Параллельные конструкции существуют таким образом, что столбцы J могут быть отправлены на каждый компьютер, а отдельные столбцы вычисляются параллельно. Трудная часть распараллеливания возникает, когда у вас есть петли, содержащие зависимости.

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        //For obvious reasons, matrix index verification code removed
        m[i][j] = m[i/2][j] + m[i][j+7]; 
    }
}

Очевидно, что цикл, подобный приведенному выше, становится чрезвычайно проблематичным (обратите внимание на матричные индексы.) Но существуют методы для разворачивания этих типов циклов и создания эффективных параллельных алгоритмов.

ANSWER

Возможно, Google разработал решение для вычисления собственного значения без сохранения копии матрицы на всех подчиненных компьютерах. -Or- Они использовали что-то вроде Монте-Карло или какой-то другой Аппликационный алгоритм, чтобы разработать "достаточно близкий" расчет.

Фактически, я бы зашел так далеко, что сказал, что Google пойдет как можно дольше, чтобы сделать любой расчет, необходимый для их алгоритма PageRank как можно более эффективным. Когда вы запускаете такие машины, как эти и this (обратите внимание на кабель Ethernet), вы не можете передавать большие наборы данных (100s концертов), потому что это невозможно с учетом их аппаратных ограничений товарных карт NIC.

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

постамбула

Некоторые хорошие ресурсы для параллельных вычислений будут включать OpenMP и MPI. Обе параллельные реализации подходят к параллельным вычислениям из очень разных парадигм, некоторые из которых связаны с реализацией машины (кластер или распределенные вычисления).

Ответ 3

Я подозреваю, что он неприемлем для большинства матриц, кроме тех, которые имеют специальные структуры (например, разреженные матрицы или единицы с определенными блочными шаблонами). Там слишком много связей между матричными коэффициентами и собственными значениями.

PageRank использует очень разреженную матрицу специальной формы, и любые выводы из расчета ее собственных значений почти наверняка не распространяются на общие матрицы, (изменить: здесь другая ссылка, которая выглядит интересной)

Ответ 4

Теперь я могу ответить. Алгоритм PageRank использует преимущества разреженной матрицы, где он должен сходиться на собственном значении с несколькими самомножающимися. Таким образом, в практике PageRank действует процедура Map/Reduce. Вы можете выполнить умножение матрицы в процедуре Map и сформировать разреженную матрицу в процедуре "Уменьшить". Но для общего нахождения собственных значений матрицы, это все еще сложная задача.

Ответ 5

Проект apache hama имеет некоторую интересную реализацию алгоритма собственных значений Якоби. Он работает на хаопе. Обратите внимание, что вращение происходит при сканировании матрицы, а не в уменьшении карты.