Integer overflow for random DSCC matrices with a high dimension.

[FlorentinD]

When trying to create a random sparse matrix of size 10^6 x 10^6, a bug occurs based on an integer overflow.

Test to validate:

    @Test
    public void hugeDimensionalMatrix() {
        int dim = 1_000_000;
        RandomMatrices_DSCC.rectangle(dim, dim, dim * 4,rand);
    }

The problematic lines are (in RandomMatrices_DSCC):

nz_total = Math.min(numCols*numRows,nz_total);
int[] selected = UtilEjml.shuffled(numRows*numCols, nz_total, rand);

Here numCols*numRows produces an Integer overflow.

[FlorentinD]

To catch the overflow, we could use Math.multiplyExact(numRows, numCols), but I didn't see, how to handle this case.

[lessthanoptimal]

How often do you need matrices larger than the integer max? I've been debating what to do here since the size of Java arrays being limited to 31-bits is getting more annoying and the Java development team doesn't seem to want to move quickly on this problem.

[FlorentinD]

For graphs it can be quite often, that the adjacency matrix has such dimensions.
A typical benchmark graph is the ldbc social network graph, with 3 Million vertices as scale-factor 1.
For example a matrix sized 46341 x 46341 already produces an overflow here.

However it occurs less often, that the adjacency matrix actually stores as 2^31-1 entries (e.g. number of edges).
Random matrices are mainly used for testing right?
F.i. for benchmarking my implementations, it would be useful if I could create matrices with higher dimensions.

I also think the method should throw, when nz_total is larger than Int.MAX_VALUE (or smaller than 0).

[FlorentinD]

I could also think of having a different kind of interface for generating sparse random matrices, e.g.generate(int numRows, int numRows, int avgDegree, someEnum degreeDistribution).
With degree I mean the average amount of entries per column (maybe we could find a better word).
Possible distributions would be uniform and powerlaw.
The reasoning here is, that a powerlaw distribution is common for many real world graphs.

This idea is based on https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/graph-generation/.

[lessthanoptimal]

It now checks to see if the shape exceeds the maximum size of an integer using the function below:

   /**
     * Checks to see if a matrix of this size will exceed the maximum possible value an integer can store, which is
     * the max possible array size in Java.
     */
    public static boolean exceedsMaxMatrixSize( int numRows, int numCols ) {
        if (numRows == 0 || numCols == 0)
            return false;
        return numCols > Integer.MAX_VALUE/numRows;
    }

[lessthanoptimal]

#91

Apologies for the PR I'm linking here. I formatted the code making it extremely difficult to identify the relevant change. I'm trying to clean up the code, but only when I manually inspect a class. I should be doing this in separate commits... I'll probably be regretting this decision when I'm hunting down regressions.

[lessthanoptimal]

I like the idea of a more structured random matrix. Always thought the simple approach here was klunky. I think I would need to look at their code to really understand what they are doing. Sounds a bit complex.

[FlorentinD]

Thank you, I reviewed your PR.

Than lets say, that the rectangle behaviour will not changed (just throwing an error as in your PR), and rather create a new method, which is based on avgDegree and distribution?
So we could track the progress on the new random matrix generator in a new issue 🙂

[FlorentinD]

The uniform distribution should be fairly simple and could be a starting point.
The col_idx[] follows a simple pattern: col_idx[i+1] = col_idx[i] + avgDegree.
For the row values java.util.Random.nextInt() could be used, as its uniformely distributed.

I would try to add this simple version on the weekend.

[lessthanoptimal]

yes let's do that! Let me know when the PR is ready.

[FlorentinD]

@lessthanoptimal The PR is ready 🙂