Java에서 큰 크기의 행렬을 처리하십시오.

Question

현재 크기가 48K x 50K 인 행렬로 단일 값 분해를 수행해야합니다.

JAMA를 사용해 보았지만 행> 열에서만 작동합니다. PCOLT, JBLAS를 사용해 보았지만 열 * 열> MAX_INT 일 때 오류를 반환합니다.

어떤 제안을해야합니까?

위의 내용을 잘못 작성하면 죄송합니다.

미리 감사드립니다.

Answer 1

SVD 계산을 수행 할 때 유사한 문제가 발생했습니다. 경험치 : Java에서는 수행하지 마십시오. 이 작업을보다 효율적으로 수행 할 수있는 도구가 있습니다. Java가 실제로 필요한 경우 코드 내부에서 도구를 호출하는 인터페이스를 작성하는 것이 좋습니다. 나는 R을 사용하여 끝났다. R을 행렬로 읽을 수있는 파일에 행렬을 저장하여 수동으로 사용했습니다.

그런데 행렬이 sparse이면 메모리 사용과 출력 파일의 크기를 줄일 수있는 다양한 최적화가 가능합니다 (사용하도록 선택하는 경우).

그렇지 않으면,이 도움이 있는지 확인하기 위해이 스레드를 체크 아웃 : Handle large data structure in Java 메모리의 정말 큰 블록의 경우

Answer 2

, 나는이 작업을 수행 할 수 있습니다 (아마도이 ​​R가 당신을 위해 무엇을 것입니다) 메모리 매핑 된 파일 사용하는 것이 좋습니다 경향 Java로 보일러 플레이트 코드가 있습니다. 불행하게도 Java는 한 번에 2GB 이상의 매핑을 직접 지원하지 않으므로 섹션으로 나누어야합니다.

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

이 대각 값을 설정하는 테스트가 있습니다. 실제로 사용 (-XX:-UseTLAB으로 실행)

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

인쇄

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 단계. 다중 정면/병렬 알고리즘을 사용하십시오.

This paper 큰 SVD를위한 SOTA 방법. 3 프로세서의 Lanzcos 알고리즘은 32k x 32k 매트릭스에서 10 분 이상 걸렸지 만 가장 작은 특이 값을 나타냅니다. 연속적인 특이 값을 수축시키고 재 추출하는 것이 가능할 것입니다 - 저는 항상 Power Iteration을 발견했습니다.

즉, M X M_T와 M_T X M을 만들고 고유 벡터와 고유 값을 취하여 SVD 행렬을 재구성합니다.

근사치를 허용 할 준비가 되었다면 this other paper은 근사 알고리즘을 다루는 많은 것 중 하나 일뿐입니다. 많은 것은 기둥의 다운 샘플링이나 최적화 된 대표적인 서브 매트릭스의 일부 유형을 기반으로합니다. 여기서 부분적으로 작은 조각의 이점과 병렬 처리를 활용할 수 있습니다.

분명히 이러한 것들은 약간의 왜곡이 있지만 어쩌면 당신의 결과를 위해 부드럽게 할 수 있습니다.

마지막으로 곱셈을 수행하기 위해 Strassen의 방법을 사용해야합니다.