在Java的大型稀疏矩阵Cholesky分解(Cholesky decomposition of l

2019-10-22 15:29发布

我想要做的在Java中大型稀疏矩阵Cholesky分解。 目前我使用的并行柯尔特库类SparseDoubleCholeskyDecomposition但它比使用慢很多我的代码,我用C写了密集矩阵,我与JNI的Java使用 。

例如,对于5570x5570矩阵具有0.25%与SparseDoubleCholeskyDecomposition非零密度需要26.6秒对因子和我自己的用于使用密集存储相同的矩阵码只需要1.12秒 。 但是,如果我设置密度0.025%,那么小马库只需要0.13秒。

我一直在使用也写了我自己的稀疏矩阵Cholesky分解用C 压缩行存储和OpenMP和它颇有几分比SparseDoubleCholeskyDecomposition也更快,但仍比使用密集存储我的算法慢。 我大概可以进一步优化,但在任何情况下乔莱斯基因素密集所以它既不解决了速度也不是存储问题。

但我想在毫秒次,我最终需要将规模扩大到超过10000x10000的矩阵因此对于密集矩阵连我自己密集的代码会变得太慢,使用过多内存。

我有理由相信稀疏矩阵的Cholesky分解可以更快完成并使用更少的内存 。 也许我需要一个更好的Java库BLAS ? 是否有一个Java库,做Cholesky分解为稀疏矩阵高效? 也许我没有使用并行柯尔特最佳?

import cern.colt.matrix.tdouble.algo.decomposition.SparseDoubleCholeskyDecomposition;
import cern.colt.matrix.tdouble.impl.*;
import java.util.Random;

public class Cholesky {
    static SparseRCDoubleMatrix2D create_sparse(double[] a, int n, double r) {
        SparseRCDoubleMatrix2D result = new SparseRCDoubleMatrix2D(n, n);
        Random rand = new Random();
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {
                double c = rand.nextDouble();
                double element = c<r ? rand.nextDouble() : 0;
                a[i*n+j] = element;
                a[j*n+i] = element;
                if (element != 0) {
                    result.setQuick(i, j, element);
                    result.setQuick(j, i, element);
                }
            }
        }
        for(int i=0; i<n; i++) {
            a[i * n + i] += n;
            result.setQuick(i,i, result.getQuick(i,i) + n);
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 5570;
        //int n = 2048;
        double[] a = new double[n*n];
        SparseRCDoubleMatrix2D sparseMatrix = create_sparse(a, n, 0.0025);

        long startTime, endTime, duration;

        startTime = System.nanoTime();
        SparseDoubleCholeskyDecomposition sparseDoubleCholeskyDecomposition = new SparseDoubleCholeskyDecomposition(sparseMatrix, 0);
        endTime = System.nanoTime();
        duration = (endTime - startTime);
        System.out.printf("colt time construct %.2f s\n", 1E-9*duration);
    }
}
文章来源: Cholesky decomposition of large sparse matrices in Java