Search code examples
rperformancercppmatrix-inversecross-product

Fastest way in R to compute the inverse for large matrices


I need to compute a hat matrix (as from linear regression). Standard R code would be:

H <- tcrossprod(tcrossprod(X, solve(crossprod(X))), X)

with X being a relatively large matrix (i.e 1e5*100), and this line has to run thousands of times. I understand the most limiting part is the inverse computation, but the crossproducts may be time-consuming too. Is there any faster alternative to perform these matrix operations? I tried Rcpp and reviewed several posts but any alternative I tested was slower. Maybe I did not code properly my C++ code, as I am not an advanced C++ programmer.

Thanks!


Solution

  • Chasing the code for this line by line is a little difficult because the setup of R code is a little on the complicated side. But read on, pointers below.

    The important part is that the topic has been discussed many times: what happens is that R dispatches this to the BLAS (Basic Linear Algebra Subprogram) and LAPACK (Linear Algebra PACKage) libraries. Which contain the most efficient code known to man for this. In general, you cannot gain on it by rewriting.

    One can gain performance differences by switching one BLAS/LAPACK implementation for another---there are many, many posts on this online too. R itself comes with the so-called 'reference BLAS' known to be correct, but slowest. You can switch to Atlas, OpenBLAS, MKL, ... depending on your operating system; instructions on how to do so are in some of the R manuals that come with your installation.

    For completeness, per file src/main/names.c the commands %*%, crossprod and tcrossprod all refer to do_matprod. This is in file src/main/array.c and does much argument checking and arranging and branching on types of arguments but e.g. one path then calls

    F77_CALL(dsyrk)(uplo, trans, &nc, &nr, &one, x, &nr, &zero, z, &nc
            FCONE FCONE); 
    

    which is this LAPACK function. It is essentially the same for all others making this an unlikely venue for your optimisation.