Обработка матрицы большого размера в Java

Question

В настоящее время мне нужно выполнить декомпозицию по единственному значению с матрицей размером 48K x 50K.

Я пробовал JAMA, но он работает только для строк> столбцов.Я пробовал PCOLT, JBLAS, но они возвращают ошибку, когда строки * столбцы> MAX_INT

Любые предложения, что мне делать?

Извините, если я допустил какие-либо ошибки в вышеуказанных строках.

Заранее большое спасибо!

Answer 1

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

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

В противном случае, проверьте этот поток, чтобы увидеть, поможет ли это: Обработка большой структуры данных в Java

Answer 2

Для действительно больших блоков памяти я склоняюсь к использованию файлов с отображенной памятью (возможно, именно это и делает для вас R). Вы можете сделать это на Java с помощью некоторого кода.К сожалению, Java напрямую не поддерживает отображение более 2 ГБ за раз, поэтому вам нужно разбить его на разделы.

import sun.misc.Cleaner;
import sun.nio.ch.DirectBuffer;

import java.io.Closeable;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.util.ArrayList;
import java.util.List;

public class LargeDoubleMatrix implements Closeable {
    private static final int MAPPING_SIZE = 1 << 30;
    private final RandomAccessFile raf;
    private final int width;
    private final int height;
    private final List<MappedByteBuffer> mappings = new ArrayList<MappedByteBuffer>();

    public LargeDoubleMatrix(String filename, int width, int height) throws IOException {
        this.raf = new RandomAccessFile(filename, "rw");
        try {
            this.width = width;
            this.height = height;
            long size = 8L * width * height;
            for (long offset = 0; offset < size; offset += MAPPING_SIZE) {
                long size2 = Math.min(size - offset, MAPPING_SIZE);
                mappings.add(raf.getChannel().map(FileChannel.MapMode.READ_WRITE, offset, size2));
            }
        } catch (IOException e) {
            raf.close();
            throw e;
        }
    }

    protected long position(int x, int y) {
        return (long) y * width + x;
    }

    public int width() {
        return width;
    }

    public int height() {
        return height;
    }

    public double get(int x, int y) {
        assert x >= 0 && x < width;
        assert y >= 0 && y < height;
        long p = position(x, y) * 8;
        int mapN = (int) (p / MAPPING_SIZE);
        int offN = (int) (p % MAPPING_SIZE);
        return mappings.get(mapN).getDouble(offN);
    }

    public void set(int x, int y, double d) {
        assert x >= 0 && x < width;
        assert y >= 0 && y < height;
        long p = position(x, y) * 8;
        int mapN = (int) (p / MAPPING_SIZE);
        int offN = (int) (p % MAPPING_SIZE);
        mappings.get(mapN).putDouble(offN, d);
    }

    public void close() throws IOException {
        for (MappedByteBuffer mapping : mappings)
            clean(mapping);
        raf.close();
    }

    private void clean(MappedByteBuffer mapping) {
        if (mapping == null) return;
        Cleaner cleaner = ((DirectBuffer) mapping).cleaner();
        if (cleaner != null) cleaner.clean();
    }
}

имеет этот тест, который устанавливает диагональное значение.

@Test
public  void getSetMatrix() throws IOException {
    long start = System.nanoTime();
    final long used0 = usedMemory();
    LargeDoubleMatrix matrix = new LargeDoubleMatrix("/tmp/ldm.test", 48*1000, 50*1000);
    for(int i=0;i<matrix.width();i++)
        matrix.set(i,i,i);
    for(int i=0;i<matrix.width();i++)
        assertEquals(i, matrix.get(i,i), 0.0);
    long time = System.nanoTime() - start;
    final long used = usedMemory() - used0;
    if (used==0)
        System.err.println("You need to use -XX:-UsedTLAB to see small changes in memory usage.");
    System.out.printf("Setting the diagonal took %,d ms, Heap used is %,d KB%n", time/1000/1000, used/1024);
    matrix.close();
}

private long usedMemory() {
    return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}

отпечатков (при запуске с -XX:-UseTLAB)

Setting the diagonal took 60 ms, Heap used is 55 KB

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

$ ls -lh /tmp/ldm.test 
-rw-rw-r-- 1 peter peter 18G 2011-12-30 10:18 /tmp/ldm.test
$ du -sh /tmp/ldm.test 
222M    /tmp/ldm.test

Answer 3

Шаг 1. Используйте базу данных для ее хранения.
Шаг 2. Используйте мультифронтальный / параллельный алгоритм.

В этой статье рассматриваются методы SOTA для больших СВД. Алгоритм Ланцкоса на 3 процессорах занял немногим более 10 минут на матрице 32 К х 32 К, но только для наименьшего единственного значения. Вероятно, можно дефлировать и повторно извлекать последовательные единичные значения - я всегда находил Power Iteration с deflate подходящим для этого.

Короче говоря, сделайте M X M_T и M_T X M и возьмите собственные векторы и собственные значения, чтобы восстановить матрицы SVD.

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

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

Наконец, вам действительно нужно использовать метод Штрассена для умножения.