Эффективная модификация строк разреженной матрицы в Java

Question

Мне нужно "нормализовать" большую разреженную матрицу, чтобы сумма записей в каждой строке была равна 1. Для строк, имеющих несколько ненулевых записей, каждая запись делится на сумму строк. Для строк, которые являются нулями, каждая запись заменяется на 1/numberOfColumns (что делает матрицу значительно менее разреженной).

Если это имеет значение, моя матрица квадратная и симметричная. Сначала я работаю с "маленьким" тестовым образцом, где моя матрица имеет размер около 32K x 32K, но нам, в конечном счете, это нужно для работы с гораздо более крупными матрицами. Важное значение будет иметь как время, так и эффективность памяти (с памятью, которая более критична, чем время). До нормализации около 1% записей отличны от нуля.

После нормализации матрицы n x n ее необходимо умножить на ряд плотных матриц nxk, где k - небольшое число (<10)

В настоящее время я использую матричный пакет la4j, но я никоим образом не привязан к нему.

Я включил мой код нормализации ниже. Это ужасно медленно, в моем тестовом случае 32K x 32K. Я немного поэкспериментировал с тем, что часть, которая занимает больше всего времени, - это переустановка строк T-матрицы (мои строки t.setRow ниже).

Три вопроса:

1) Есть ли лучший пакет или лучший подход для эффективного выполнения этого?

2) я не должен использовать разреженное матричное представление для этого?

3) Было бы лучше не заменять нулевые строки, а просто отслеживать, какие строки были нулями, а затем соответственно взламывать умножение матриц?

Заранее спасибо!

SparseMatrix t = new CRSMatrix(n, n);

// in between non-zero entries in t are added one at a time


double uniformWeight = (double) 1 / n; // used when the rowSum is zero
    for (int i = 0; i < n; i++) {
        Vector row = t.getRow(i);
        double rowSum = row.sum();
        if (rowSum > 0) {
            row = row.divide(rowSum);
            t.setRow(i,row);
        } else {
            row.assign(uniformWeight); // Assigns all elements of this vector to given value
            t.setRow(i, row);
        }
    }

Обновление 1

Вот то, что я попробовал, ускорило процесс. Я еще не попробовал предложения Владимира, но добавлю их, когда вернусь к этому проекту на следующей неделе. Теперь я сохраняю логический массив, строки которого равны нулю, и должны рассматриваться как однородные строки во время умножения матрицы, что теперь делается с помощью моего метода hackMultiply. Буду признателен за дополнительные советы Владимира (или других людей) getRow а также setRow в этом методе. Обратите внимание, что m2 (второй мультипликатор) и m3 (матрица результатов) не разрежены, если это имеет значение. Заранее спасибо!

    boolean[] zeroRows = new boolean[n]; // all values default to false
    for (int i = 0; i < n; i++) {
        Vector row = t.getRow(i);  // haven't had a chance to try Vladimir's 
        double rowSum = row.sum(); // improvements here yet
        if (rowSum > 0) {
            row = row.divide(rowSum);  // or here
            t.setRow(i,row);           // ...
        } else {
            // instead of setting to uniform weight, just keep track
            zeroRows[i] = true;
        }
    }

/**
 * Multiplies the given matrices m1 (Sparse) and m2, with the following modifications
 * For every row in m1 for which the corrresponding entry in zeroRows is true
 * use uniformVector instead of the actual contents of the row for the multiplication
 * (Meant for the case when the replaced rows are all zeros, and we don't want 
 * to actually replace them in the SparseMatrix because then it wouldn't be sparse 
 * anymore.)
 * 
 * @param m1 First multiplicand
 * @param m2 Second multiplicand
 * @param zeroRows boolean array indicating which rows of m1 should be logically replaced by uniformVector
 * @param uniformVector vector to replace all the zeroRows with during the multiplication
 * @return the result of the hacked multiplication
 */
public static Matrix hackMultiply(SparseMatrix m1, Matrix m2, boolean[] zeroRows, Vector uniformVector) {
// for "efficiency" I'm assuming I get passed in things of appropriate sizes, no checking
    int a = m1.rows();
    int b = m2.columns();
    int c = m1.columns(); // must == m2.rows() for the matrix multiplication to work
    Matrix m3 = new Basic2DMatrix(a,b);
    Vector v1;
    for (int i = 0; i < a; i++) {
        if (zeroRows[i]) {
            v1 = uniformVector;
        } else {
            v1 = m1.getRow(i);
        }
        m3.setRow(i, v1.multiply(m2));
    }
    return m3;
}

Обновление 2

Я действительно ценю всю помощь @Vladimir и @mikera. Для чего стоит, версия использует la4j с hackMultiply подход в значительной степени идентичен по времени использования версии с использованием vectorz версия 0.26.0. Похоже, что обновления в 0.27.0 дадут ему небольшое преимущество, но я еще не пробовал. Что касается памяти, версия la4j с хаком значительно лучше, чем версия vectorz, по крайней мере, так, как я сейчас написал код. Я подозреваю, что релиз 0.27.0 также может помочь.

Answer 1

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

• Разреженное хранение данных
• Облегченные изменяемые "представления", так что вы можете изменять строки матрицы как векторы на месте

Стратегия, которую я бы использовал:

• Создать VectorMatrixMN хранить матрицу как коллекцию разреженных векторных строк
• Использовать SparseIndexedVector для каждой строки, которая является эффективным форматом для данных, в основном нулевых

Нормализация строк матрицы может быть выполнена с помощью следующего кода:

VectorMatrixMN m = ....

for (int i=0; i<SIZE; i++) {
    AVector row=m.getRow(i);
    double sum=row.elementSum();
    if (sum>0) {
        row.divide(sum);
    } else {
        m.setRow(i, new RepeatedElementVector(SIZE,1.0/SIZE));
    }
}

Обратите внимание, что этот код изменяет строки на месте, поэтому вам не нужно ничего делать, например, "setRow", чтобы вернуть данные обратно в матрицу.

Используя эту конфигурацию с разреженной матрицей 32 000 x 32 000 и плотностью 100 ненулевых значений на строку, я рассчитал это на время менее 32 мс, чтобы нормализовать всю матрицу с этим кодом (т.е. около 10 нс на ненулевой элемент == 0,03 нс). за элемент матрицы: так что вы явно получаете большие выгоды, используя разреженность).

Вы также можете по желанию использовать ZeroVector для строк с нулевым значением (они будут еще быстрее, но налагают некоторые дополнительные ограничения, поскольку ZeroVectors неизменны.....)

РЕДАКТИРОВАТЬ:

Я написал полный пример, который демонстрирует использование разреженных матриц для варианта использования, очень похожего на этот вопрос:

• https://github.com/mikera/vectorz/blob/develop/src/test/java/example/SparseMatrix.java

Answer 2

Я автор библиотеки la4j. Я вижу несколько мест для улучшения вашего кода. Вот мой совет:

призвание getRow (так же как setRow) всегда плохая идея (особенно для разреженных матриц), поскольку она запускает полное копирование строки матрицы. Я бы посоветовал вам избегать таких звонков. Таким образом, без getRow/setRow код должен выглядеть так:

SparseMatrix t = new CRSMatrix(n, n);

double uniformWeight = (double) 1 / n; // used when the rowSum is zero
for (int i = 0; i < n; i++) {
  double rowSum = t.foldRow(i, Matrices.asSumAccumulator(0.0));
  if (rowSum > 0.0) {
    MatrixFunction divider = Matrices.asDivFunction(rowSum);
    for (int j = 0; j < n; j++) {
      // TODO: I should probably think about `updateRow` method
      //       in order to avoid this loop
      t.update(i, j, divider);
    }
  } else {
    for (int j = 0; j < n; j++) {
      t.set(i, j, uniformWeight);
    }
  }
}

Пожалуйста, попробуйте это. Я не скомпилировал его, но он должен работать.

Обновить

Использование логического массива для отслеживания одних и тех же строк - фантастическая идея. Основным узким местом здесь является петля:

for (int j = 0; j < n; j++) {
  t.set(i, j, uniformWeight);
}

Здесь мы полностью разрушаем производительность / занимаемую площадь разреженной матрицы с момента присвоения всей строке одного и того же значения. Итак, я бы сказал, объединяя эти две идеи вместе: избегать getRow/setRow + дополнительный массив с флагами (я бы использовал BitSet вместо этого, он намного эффективнее с точки зрения занимаемой площади) должен дать вам потрясающую производительность.

Спасибо за использование библиотеки la4j, и, пожалуйста, сообщайте о любых проблемах с производительностью / функционалом в список рассылки или на страницу GitHub. Все ссылки доступны здесь: http://la4j.org/.