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

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

Если матрица NxM A описывает вес звена (объем потока) от узла n к узлу m, то

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

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

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

Вы можете увидеть работающую реализацию рейтинга страниц в библиотеке wukong (потоковая передача hadoop для ruby) или в подмодуле рейтинга страниц Heretrix. (Код Heretrix работает независимо от Heretrix)

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

ПРЕАМБУЛА:

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

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

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]; 
    }
}

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

ОТВЕТ:

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

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

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

ОТПРАВКА:

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

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

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

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

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