ordering.Rd
Extract the (inverse) permutation used by the Cholesky decomposition
ordering( x, inv=FALSE)
object of class spam.chol.
method returned by the function
chol
.
Return the permutation (default) or inverse thereof.
Recall that calculating a Cholesky factor from a sparse matrix
consists of finding a permutation first, then calculating the factors
of the permuted matrix. The ordering is important when working with
the factors themselves.
The ordering from a full/regular matrix is 1:n
.
Note that there exists many different algorithms to find
orderings.
See the examples, they speak more than 10 lines.
# Construct a pd matrix S to work with (size n)
n <- 100 # dimension
S <- .25^abs(outer(1:n,1:n,"-"))
S <- as.spam( S, eps=1e-4)
I <- diag(n) # Identity matrix
cholS <- chol( S)
ord <- ordering(cholS)
iord <- ordering(cholS, inv=TRUE)
R <- as.spam( cholS ) # R'R = P S P', with P=I[ord,],
# a permutation matrix (rows permuted).
RtR <- t(R) %*% R
# the following are equivalent:
as.spam( RtR - S[ord,ord], eps=1e-15)
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
as.spam( RtR[iord,iord] - S, eps=1e-15)
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
as.spam( t(R[,iord]) %*% R[,iord] - S, eps=1e-15)
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
# we use 'eps' to avoid issues close to machine precision
# trivially:
as.spam( t(I[iord,]) - I[ord,]) # (P^-1)' = P
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
as.spam( t(I[ord,]) - I[,ord]) #
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
as.spam( I[iord,] - I[,ord])
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
as.spam( I[ord,]%*%S%*%I[,ord] - S[ord,ord] )
#> Zero matrix of dimension 100x100.
#>
#> Class 'spam' (32-bit)
# pre and post multiplication with P and P' is ordering