Fast matrix inversion

Very similar to what has been done to create a function to perform fast multiplication of large matrices using the Strassen algorithm (see previous post), now we write the functions to quickly calculate the inverse of a matrix.

To avoid rewriting pages and pages of comments and formulas, as I did for matrix multiplication, this time I'll show you directly the code of the function (the reasoning behind it is quite similar). Please, copy and paste all the code in an external editor to see it properly.

Function strassenInv(A)

strassenInv <- function(A){

 div4 <- function(A, r){
  A <- list(A)
  A11 <- A[[1]][1:(r/2),1:(r/2)]
  A12 <- A[[1]][1:(r/2),(r/2+1):r]
  A21 <- A[[1]][(r/2+1):r,1:(r/2)]
  A22 <- A[[1]][(r/2+1):r,(r/2+1):r]
  A <- list(X11=A11, X12=A12, X21=A21, X22=A22)
  return(A)
 }

        if (nrow(A) != ncol(A)) 
          { stop("only square matrices can be inverted") }

 is.wholenumber <-
     function(x, tol = .Machine$double.eps^0.5)  abs(x - round(x)) < tol

 if ( (is.wholenumber(log(nrow(A), 2)) != TRUE) || (is.wholenumber(log(ncol(A), 2)) != TRUE) )
   { stop("only square matrices of dimension 2^k * 2^k can be inverted with Strassen method") }

 A <- div4(A, dim(A)[1])

 R1 <- solve(A$X11)
 R2 <- A$X21 %*% R1
 R3 <- R1 %*% A$X12
 R4 <- A$X21 %*% R3
 R5 <- R4 - A$X22
 R6 <- solve(R5)
 C12 <- R3 %*% R6
 C21 <- R6 %*% R2
 R7 <- R3 %*% C21
 C11 <- R1 - R7
 C22 <- -R6
 
 C <- rbind(cbind(C11,C12), cbind(C21,C22))

 return(C)
}

Function strassenInv2(A)

strassenInv2 <- function(A){

 div4 <- function(A, r){
  A <- list(A)
  A11 <- A[[1]][1:(r/2),1:(r/2)]
  A12 <- A[[1]][1:(r/2),(r/2+1):r]
  A21 <- A[[1]][(r/2+1):r,1:(r/2)]
  A22 <- A[[1]][(r/2+1):r,(r/2+1):r]
  A <- list(X11=A11, X12=A12, X21=A21, X22=A22)
  return(A)
 }

 strassen <- function(A, B){
  A <- div4(A, dim(A)[1])
  B <- div4(B, dim(B)[1])
  M1 <- (A$X11+A$X22) %*% (B$X11+B$X22)
  M2 <- (A$X21+A$X22) %*% B$X11
  M3 <- A$X11 %*% (B$X12-B$X22)
  M4 <- A$X22 %*% (B$X21-B$X11)
  M5 <- (A$X11+A$X12) %*% B$X22
  M6 <- (A$X21-A$X11) %*% (B$X11+B$X12)
  M7 <- (A$X12-A$X22) %*% (B$X21+B$X22)

  C11 <- M1+M4-M5+M7
  C12 <- M3+M5
  C21 <- M2+M4
  C22 <- M1-M2+M3+M6
 
  C <- rbind(cbind(C11,C12), cbind(C21,C22))
  return(C)
 }

        if (nrow(A) != ncol(A)) 
          { stop("only square matrices can be inverted") }

 is.wholenumber <-
     function(x, tol = .Machine$double.eps^0.5)  abs(x - round(x)) < tol

 if ( (is.wholenumber(log(nrow(A), 2)) != TRUE) || (is.wholenumber(log(ncol(A), 2)) != TRUE) )
   { stop("only square matrices of dimension 2^k * 2^k can be inverted with Strassen method") }

 A <- div4(A, dim(A)[1])

 R1 <- strassenInv(A$X11)
 R2 <- strassen(A$X21 , R1)
 R3 <- strassen(R1 , A$X12)
 R4 <- strassen(A$X21 , R3)
 R5 <- R4 - A$X22
 R6 <- strassenInv(R5)
 C12 <- strassen(R3 , R6)
 C21 <- strassen(R6 , R2)
 R7 <- strassen(R3 , C21)
 C11 <- R1 - R7
 C22 <- -R6
 
 C <- rbind(cbind(C11,C12), cbind(C21,C22))

 return(C)
}

Function strassenInv3(A)

strassenInv3 <- function(A){

 div4 <- function(A, r){
  A <- list(A)
  A11 <- A[[1]][1:(r/2),1:(r/2)]
  A12 <- A[[1]][1:(r/2),(r/2+1):r]
  A21 <- A[[1]][(r/2+1):r,1:(r/2)]
  A22 <- A[[1]][(r/2+1):r,(r/2+1):r]
  A <- list(X11=A11, X12=A12, X21=A21, X22=A22)
  return(A)
 }

 strassen <- function(A, B){
  A <- div4(A, dim(A)[1])
  B <- div4(B, dim(B)[1])
  M1 <- (A$X11+A$X22) %*% (B$X11+B$X22)
  M2 <- (A$X21+A$X22) %*% B$X11
  M3 <- A$X11 %*% (B$X12-B$X22)
  M4 <- A$X22 %*% (B$X21-B$X11)
  M5 <- (A$X11+A$X12) %*% B$X22
  M6 <- (A$X21-A$X11) %*% (B$X11+B$X12)
  M7 <- (A$X12-A$X22) %*% (B$X21+B$X22)

  C11 <- M1+M4-M5+M7
  C12 <- M3+M5
  C21 <- M2+M4
  C22 <- M1-M2+M3+M6
 
  C <- rbind(cbind(C11,C12), cbind(C21,C22))
  return(C)
 }

 strassen2 <- function(A, B){
  A <- div4(A, dim(A)[1])
  B <- div4(B, dim(B)[1])
  M1 <- strassen((A$X11+A$X22) , (B$X11+B$X22))
  M2 <- strassen((A$X21+A$X22) , B$X11)
  M3 <- strassen(A$X11 , (B$X12-B$X22))
  M4 <- strassen(A$X22 , (B$X21-B$X11))
  M5 <- strassen((A$X11+A$X12) , B$X22)
  M6 <- strassen((A$X21-A$X11) , (B$X11+B$X12))
  M7 <- strassen((A$X12-A$X22) , (B$X21+B$X22))

  C11 <- M1+M4-M5+M7
  C12 <- M3+M5
  C21 <- M2+M4
  C22 <- M1-M2+M3+M6

  C <- rbind(cbind(C11,C12), cbind(C21,C22))
  return(C)
 }

        if (nrow(A) != ncol(A)) 
          { stop("only square matrices can be inverted") }

 is.wholenumber <-
     function(x, tol = .Machine$double.eps^0.5)  abs(x - round(x)) < tol

 if ( (is.wholenumber(log(nrow(A), 2)) != TRUE) || (is.wholenumber(log(ncol(A), 2)) != TRUE) )
   { stop("only square matrices of dimension 2^k * 2^k can be inverted with Strassen method") }

 A <- div4(A, dim(A)[1])

 R1 <- strassenInv2(A$X11)
 R2 <- strassen2(A$X21 , R1)
 R3 <- strassen2(R1 , A$X12)
 R4 <- strassen2(A$X21 , R3)
 R5 <- R4 - A$X22
 R6 <- strassenInv2(R5)
 C12 <- strassen2(R3 , R6)
 C21 <- strassen2(R6 , R2)
 R7 <- strassen2(R3 , C21)
 C11 <- R1 - R7
 C22 <- -R6
 
 C <- rbind(cbind(C11,C12), cbind(C21,C22))

 return(C)
}

We run now some test. First check if the function successfully invert the matrix and compare them with the results of the standard R function (Function solve()):

A <- matrix(trunc(rnorm(512*512)*100), 512,512)

all( round(solve(A),8) == round(strassenInv(A),8) )
[1] TRUE

all( round(solve(A),8) == round(strassenInv2(A),8) )
[1] TRUE

all( round(solve(A),6) == round(strassenInv3(A),6) )
[1] TRUE

The function performs the operations correctly. But there is a problem of approximation: in fact the first two functions are accurate to the eighth decimal place, while the third through sixth. Probably not an issue of calculus, but it is a problem of expression of numbers in binary format and 32-bit, which causes these errors.

Now we analyze the computation time. See in the table the result, obtained by running the following code:

Time computation

A <- matrix(trunc(rnorm(512*512)*100), 512,512)
system.time(solve(A))
system.time(strassenInv(A))
system.time(strassenInv2(A))
system.time(strassenInv3(A))

A <- matrix(trunc(rnorm(1024*1024)*100), 1024,1024)
system.time(solve(A))
system.time(strassenInv(A))
system.time(strassenInv2(A))
system.time(strassenInv3(A))

A <- matrix(trunc(rnorm(2048*2048)*100), 2048,2048)
system.time(solve(A))
system.time(strassenInv(A))
system.time(strassenInv2(A))
system.time(strassenInv3(A))

A <- matrix(trunc(rnorm(4096*4096)*100), 4096,4096)
system.time(solve(A))
system.time(strassenInv(A))
system.time(strassenInv2(A))
system.time(strassenInv3(A))

The results are quite obvious, and using a modification of Strassen algorithm for matrix inversion, there is a real time saving.

Please, remember these two recommendations already made:
- The code is to be improved, and if anyone wants to help me, I will be happy to update my code
- If you consider it useful to use these function for any work, a citation is always welcome (contact me at my e-mail for details)

Fast matrix multiplication in R: Strassen's algorithm

I tried to implement the Strassen's algorithm for big matrices multiplication in R.

Here I present a pdf with some theory element, some example and a possible solution in R.
I'm not a programmer, so the function is not optimize, but it works.

I want to thank G. Grothendieck: suggested me a very nice way on StackOverFlow to create a bigger square matrix starting from small one.

This is just a first version of the function; it needs more work on it. If someone want to collaborate, I'll be very happy.
Finally if you find my code useful for your work, I'd love to be cited (ask me via e-mail how to cite me: todoslogos -at- gmail . com).

Convert decimal to IEEE-754 in R

For some theory on the standard IEEE-754, you can read the Wikipedia page. Here I will post only the code of the function to make the conversion in R.


First we write some functions to convert decimal numbers to binary numbers:


decInt_to_8bit <- function(x, precs) {
q <- c()
r <- c()
xx <- c()
for(i in 1:precs){
xx[1] <- x
q[i] <- xx[i] %/% 2
r[i] <- xx[i] %% 2
xx[i+1] <- q[i]
}
rr <- rev(r)
return(rr)
}

devDec_to_8bit <- function(x, precs) {
nas <- c()
nbs <- c()
xxs <- c()
for(i in 1:precs)
{
xxs[1] <- x*2
nas[i] <- (xxs[i]) - floor(xxs[i])
nbs[i] <- trunc(xxs[i], 1)
xxs[i+1] <- nas[i]*2
}
return(nbs)
}


For example, in 8-bit:


decInt_to_8bit(11, 8)
[1] 0 0 0 0 1 0 1 1




devDec_to_8bit(0.625, 8)
[1] 1 0 1 0 0 0 0 0




devDec_to_8bit(0.3, 8)
[1] 0 1 0 0 1 1 0 0
devDec_to_8bit(0.3, 16)
[1] 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0


We can delete the extra-zeros from the vectors, using these functions:


remove.zero.aft <- function(a) {
n <- length(a)
for(i in n:1){
if (a[n]==0) a <- a[-n]
else return(a)
n <- n-1
}
}

remove.zero.bef <- function(a) {
n <- length(a)
for(i in 1:n){
if (a[1]==0) a <- a[-1]
else return(a)
}
}


So we have:


remove.zero.bef(decInt_to_8bit(11, 8))
[1] 1 0 1 1

remove.zero.aft(devDec_to_8bit(0.625, 8))
[1] 1 0 1


Binding these functions, we have:


dec.to.nbit <- function(x,n) {
aa <- abs(trunc(x, 1))
bb <- abs(x) - abs(trunc(x))

q <- c()
r <- c()
xx <- c()
for(i in 1:n){
xx[1] <- aa
q[i] <- xx[i] %/% 2
r[i] <- xx[i] %% 2
xx[i+1] <- q[i]
}
rr <- rev(r)

nas <- c()
nbs <- c()
xxs <- c()
for(i in 1:n)
{
xxs[1] <- bb*2
nas[i] <- (xxs[i]) - floor(xxs[i])
nbs[i] <- trunc(xxs[i], 1)
xxs[i+1] <- nas[i]*2
}

bef <- paste(remove.zero.bef(rr), collapse="")
aft <- paste(remove.zero.aft(nbs), collapse="")
bef.aft <- c(bef, aft)
strings <- paste(bef.aft, collapse=".")
return(strings)
}


Example:


dec.to.nbit(11.625,8)
[1] "1011.101"


---

Now we can write the code for the decimal to IEEE-754 single float conversion in R:


dec.to.ieee754 <- function(x) {
aa <- abs(trunc(x, 1))
bb <- abs(x) - abs(trunc(x))

rr <- decInt_to_8bit(aa, 32)

ppc <- 24 - length(remove.zero.bef(rr))

nbs <- devDec_to_8bit(bb, ppc)

bef <- remove.zero.bef(rr)
aft <- remove.zero.aft(nbs)

exp <- length(bef) - 1
mantissa <- c(bef[-1], aft)

exp.bin <- decInt_to_8bit(exp + 127, 16)
exp.bin <- remove.zero.bef(exp.bin)

first <- c()
if (sign(x)==1) first=c(0)
if (sign(x)==-1) first=c(1)

ieee754 <- c(first, exp.bin, mantissa, rep(0, 23-length(mantissa)))
ieee754 <- paste(ieee754, collapse="")

return(ieee754)
}


The numbers 11.625 and 11.33 in IEEE-754 are:


dec.to.ieee754(11.625)
[1] "01000001001110100000000000000000"

dec.to.ieee754(11.33)
[1] "01000001001101010100011110101110"


You can verify the output with this Online Binary-Decimal Converter