Manejar una matriz de gran tamaño en Java

Question

Actualmente necesito hacer una descomposición de valores singulares con una matriz de tamaño 48K x 50K.

He intentado con JAMA pero solo funciona para filas> columnas. He intentado PCOLT, JBLAS pero devuelven el error cuando filas * columnas> MAX_INT

¿Alguna sugerencia qué debo hacer?

Lo siento si he cometido algún error en las líneas anteriores.

¡Muchas gracias de antemano!

Answer 1

Tuve problemas similares al realizar cálculos SVD y mi experiencia es: no hagas esto en Java. Hay herramientas disponibles que pueden hacer esto de manera más eficiente. Si realmente necesita Java, puede considerar construir una interfaz que llame a la herramienta desde su código. Terminé usando R. Lo usé manualmente al almacenar la matriz en un archivo que podría leer R como una matriz.

Por cierto, si la matriz es sparse, hay varias optimizaciones posibles que reducirían el uso de memoria y el tamaño del archivo de salida (si elige usar uno).

De lo contrario, echa un vistazo a este hilo para ver si eso ayuda: Handle large data structure in Java

Answer 2

Para realmente grandes bloques de memoria, que tienden a sugerir el uso de archivos de memoria mapeada (tal vez esto es lo que hace R para usted) Usted puede hacer esto en Java con un código de placa de caldera. Desafortunadamente, Java no admite directamente el mapeo de más de 2 GB a la vez, por lo que debe dividirlo en secciones.

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(); 
    } 
} 

tiene esta prueba que establece el valor diagonal. Se crean

@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(); 
} 

impresiones (cuando se ejecuta con -XX:-UseTLAB)

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

sólo las páginas utilizadas realidad. Los archivos parecen ser muy grandes, pero el espacio asignado se basa en el uso.

$ 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

Paso 1. Usa una base de datos para contenerlo.
Paso 2. Usa un algoritmo multi-frontal/paralelo.

This paper encuestas Métodos SOTA para SVD grandes. El algoritmo de Lanzcos en 3 procesadores tomó algo más de 10 minutos en una matriz de 32k X 32k, pero solo para el valor singular más pequeño. Probablemente sea posible desinflar y volver a extraer valores singulares sucesivos. Siempre he encontrado que Power Iteration with deflate es buena para esto.

En resumen, cree M X M_T y M_T X M y tome los vectores propios y los valores propios para reconstruir las matrices SVD.

Si está preparado para aceptar aproximaciones, this other paper es solo una de las muchas que trata sobre algoritmos aproximados. Muchos se basan en algún tipo de reducción del muestreo de las columnas, o de submatrices óptimamente representativas, donde se aprovecha el beneficio de piezas más pequeñas para trabajar, más el paralelismo.

Obviamente, estos vienen con cierta distorsión, pero tal vez pueda suavizar su resultado.

Por último, realmente necesitas usar el método de Strassen para hacer las multiplicaciones.