[Ether]

Originally Posted by Caleb Sykes

The problem is that this method requires A to be square, which it isn't.

Stacy created N = A'A, which is square. See below.

you converted the A matrix into a sparse matrix

No. I created a sparse matrix representation of the design matrix A directly from the raw qual score data, in one pass through the raw data, with no nested loops, and with no intermediate dense matrix. This is where the bulk of the time savings is. The b and T vectors are created in the same single pass that creates the sparse design matrix. See below.


Let A be the 17842-by-2696 dichotomous (ones and zeros) design matrix of the overdetermined linear system
corresponding to the raw qual match data (alliances & scores) in the file "8col Hill.dat".

Let b be the 17842-by-1 column vector of alliance scores

Let N be the 2696-by-2696 matrix of the coefficients of the normal equations N=A'A

Let d be A'b

Using Stacy's R code as a dense matrix performance baseline, it takes 10 seconds to create the N matrix and d vector, and another 3 seconds to compute the OPR from Nx=d

Using sparse matrix technology, it takes 0.68 seconds to create the b column vector and the sparse matrix A, and 0.27 seconds to compute OPR from Ax=b.