HMLP: High-performance Machine Learning Primitives
Public Member Functions | Public Attributes | List of all members
hmlp::gofmm::Factor< T > Class Template Reference

#include <igofmm.hpp>

Inheritance diagram for hmlp::gofmm::Factor< T >:
hmlp::gofmm::NodeData< T >

Public Member Functions

void SetupFactor (bool issymmetric, bool do_ulv_factorization, bool isleaf, bool isroot, size_t n, size_t nl, size_t nr, size_t s, size_t sl, size_t sr)
 
void SetupFactor (bool issymmetric, bool do_ulv_factorization, bool isleaf, bool isroot, size_t n, size_t nl, size_t nr, size_t s, size_t sl, size_t sr, Data< T > &U, Data< T > &V)
 
bool DoULVFactorization ()
 
bool IsSymmetric ()
 
void CheckCondition ()
 
void Factorize (Data< T > &Kaa)
 
void PartialFactorize (Data< T > &A)
 
void Factorize (Data< T > &Ul, Data< T > &Ur, Data< T > &Vl, Data< T > &Vr)
 
void PartialFactorize (View< T > &Zl, View< T > &Zr, Data< T > &Ul, Data< T > &Ur, Data< T > &Vl, Data< T > &Vr)
 
void Multiply (View< T > &bl, View< T > &br)
 
void Solve (View< T > &rhs)
 Solver for leaf nodes. More...
 
void Solve (View< T > &bl, View< T > &br)
 b - U * inv( Z ) * C * V' * b More...
 
void Telescope (bool DO_INVERSE, Data< T > &Pa, Data< T > &Palr)
 
void Telescope (bool DO_INVERSE, Data< T > &Pa, Data< T > &Palr, Data< T > &Pl, Data< T > &Pr)
 
void Orthogonalization ()
 
void ChangeBasis (SideType side, Data< T > &B)
 
void ChangeBasis (Data< T > &A)
 
void ULVForward ()
 
void ULVBackward ()
 

Public Attributes

bool isleaf = false
 
bool isroot = false
 
size_t n = 0
 
size_t nl = 0
 
size_t nr = 0
 
size_t s = 0
 
size_t sl = 0
 
size_t sr = 0
 
Data< T > Z
 
View< T > Zv
 
View< T > Ztl
 
View< T > Ztr
 
View< T > Zbl
 
View< T > Zbr
 
vector< int > ipiv
 
Data< T > U
 
Data< T > V
 
Data< T > Crl
 
Data< T > Clr
 
View< T > bview
 
Data< T > * Ul = NULL
 
Data< T > * Ur = NULL
 
Data< T > * Vl = NULL
 
Data< T > * Vr = NULL
 
Data< T > Q
 
View< T > Qv
 
View< T > Q1
 
View< T > Q2
 
vector< T > tau
 
Data< T > B
 
View< T > Bv
 
View< T > Bp
 
View< T > Bsibling
 
View< T > Bf
 
View< T > Bc
 

Detailed Description

template<typename T>
class hmlp::gofmm::Factor< T >

for each level for each alpha

if ( leaf )

LL' = Chol( Kaa ) U = inv( L ) * proj' or U' = proj * inv( L' ) QR = qr( U ) or LQ' = lq( U' )

else

LL' = Chol( I + k.R * C * k.R' )

if ( not root )

U = inv( L ) * [ l.R * proj' or r.R ] U' = proj' * [ l.R * inv( L' ) r.R ] QR = qr( U ) or LQ' = lq( U' )

Member Function Documentation

template<typename T >
void hmlp::gofmm::Factor< T >::ChangeBasis ( SideType  side,
Data< T > &  B 
)
inline

[Q2 Q1]' * B or B * [Q2 Q1]

Early return if Q does not exist.

Create a deep copy of B.

Create matrix views for A and B.

Enumerate case "LEFT", "RIGHT", and execptions.

Partition Bv = [ Bt; Bb ].

Bt = Q2' * A

Bb = Q1' * A

Partition Bv = [ Bl, Br ].

Bl = A * Q2

Br = A * Q1

Do nothing and throw exception.

template<typename T >
void hmlp::gofmm::Factor< T >::ChangeBasis ( Data< T > &  A)
inline

changeBasis() [Q2 Q1]' * A * [Q2 Q1]

template<typename T >
void hmlp::gofmm::Factor< T >::Factorize ( Data< T > &  Kaa)
inline

Initialize with Kaa.

Record the partial pivoting order.

Compute 1-norm of Z.

Pivoted LU factorization.

Compute 1-norm condition number.

template<typename T >
void hmlp::gofmm::Factor< T >::Factorize ( Data< T > &  Ul,
Data< T > &  Ur,
Data< T > &  Vl,
Data< T > &  Vr 
)
inline

end PartialFactorize() two-sided UCVt one-sided UBt

| sl sr | sl sr

nl | Ul nl | Ul nr | Ur nr | Ur

| sl sr

sl | Clr sr | Crl

| nl nr | nl nr

sl | Vlt sl | Brt sr | Vrt sr | Blt

even SYMMETRIC this routine uses LU factorization

clean up and begin with Z = eye( sl + sr ) = | sl sr

sl | Zrl Ztr sr | Zbl Zbr

Z = I + UR * C * VR' = [ I URl * Clr * VRr' URr * Crl * VRl' I ]

Cholesky

Zbl = URr * Crl * VRl'

trmm

trmm

Zbl

LL' = potrf( Z )

pivoting row indices

LU

pivoting row indices

Sherman-Morrison-Woodbury

pivoting row indices

Z = I + CVtU = [ I ClrVrtUr CrlVltUl I ]

VltUl

VrtUr

CrlVltUl

Crl'VrtUr

ClrVrtUr

compute 1-norm of Z

LU factorization

record points of children factors

compute 1-norm condition number

Parameters
UlUl, nl-by-sl
UrUr, nr-by-sr
VlVl, nl-by-sr
VrVr, nr-by-sr
template<typename T >
void hmlp::gofmm::Factor< T >::Multiply ( View< T > &  bl,
View< T > &  br 
)
inline

end PartialFactorize()

Vl' * bl

Vr' * br

Crl * Vl' * bl

Crl' * Vr' * br

Clr * Vr' * br

bl += Ul * xl

br += Ur * xr

template<typename T >
void hmlp::gofmm::Factor< T >::Orthogonalization ( )
inline

Initialize householder reflectors "tau".

Initialize work space for xgeqrf.

QR factorization without column pivoting.

Copy U to Q to generate the full orthonormal basis.

Increase the rank of Q to full rank.

Generate the full orthonormal basis Q.

Create views Qv = [Q1, Q2] for Q.

Sanity check for Q1'Q1 and Q2'Q2 and Q1'Q2.

template<typename T >
void hmlp::gofmm::Factor< T >::PartialFactorize ( Data< T > &  A)
inline

end Factorize() Kaa = [ P [ L11 [ I [ U11 U12 I ] L21 I ] C ] I ]

Similar transformation ( Q' * Z * Q ).

Create matrix views for Z.

Initialize pivoting rows.

[Ztl, Ztr] = PLU

Zbl * U^{-1}

Update Schur complement Zbr.

template<typename T >
void hmlp::gofmm::Factor< T >::PartialFactorize ( View< T > &  Zl,
View< T > &  Zr,
Data< T > &  Ul,
Data< T > &  Ur,
Data< T > &  Vl,
Data< T > &  Vr 
)
inline

end Factorize()

Create matrix views for Z.

trmm

trmm

Parameters
ZlZl, nl-by-nl, Zr, nr-by-nr
UlUl, nl-by-sl, Ur, nr-by-sr
VlVl, nl-by-sr, Vr, nr-by-sr
template<typename T >
void hmlp::gofmm::Factor< T >::SetupFactor ( bool  issymmetric,
bool  do_ulv_factorization,
bool  isleaf,
bool  isroot,
size_t  n,
size_t  nl,
size_t  nr,
size_t  s,
size_t  sl,
size_t  sr 
)
inline
Parameters
nn == nl + nr (left + right)
ss <= sl + sr
template<typename T >
void hmlp::gofmm::Factor< T >::SetupFactor ( bool  issymmetric,
bool  do_ulv_factorization,
bool  isleaf,
bool  isroot,
size_t  n,
size_t  nl,
size_t  nr,
size_t  s,
size_t  sl,
size_t  sr,
Data< T > &  U,
Data< T > &  V 
)
inline
Parameters
Un-by-?; its rank depends on mu sibling
V?-by-n; its rank depends on my sibling
template<typename T >
void hmlp::gofmm::Factor< T >::Solve ( View< T > &  rhs)
inline

Solver for leaf nodes.

assure this is a leaf node

LU solver

template<typename T >
void hmlp::gofmm::Factor< T >::Solve ( View< T > &  bl,
View< T > &  br 
)
inline

b - U * inv( Z ) * C * V' * b

end Solve()

assertion

buffer

views of buffer

xa = [ xl; xr; ]

Vl' * bl

Vr' * br

Crl * Vl' * bl

Crl' * Vr' * br

Clr * Vr' * br

inv( Z ) * x

bl -= Ul * xl

br -= Ur * xr

template<typename T >
void hmlp::gofmm::Factor< T >::Telescope ( bool  DO_INVERSE,
Data< T > &  Pa,
Data< T > &  Palr 
)
inline

end Solve()

Initialize Pa

create view and subviews for Pa

Pa = Palr'

LU solver

Parameters
Pan-by-s
Palrs-by-(sl+sr)
template<typename T >
void hmlp::gofmm::Factor< T >::Telescope ( bool  DO_INVERSE,
Data< T > &  Pa,
Data< T > &  Palr,
Data< T > &  Pl,
Data< T > &  Pr 
)
inline

end Telescope() RIGHT: V = [ P(:, 0:st-1) * Vl , P(:,st:st+sb-1) * Vr ] LEFT: U = [ Ul * P(:, 0:st-1)'; Ur * P(:,st:st+sb-1) ]

Initialize Pa

create view and subviews for Pa

Pa = Palr'

Pa( 0:sl-1, : ) = Pl * Palr( :, 0:sl-1 )'

Pa( sl:sl+sr-1, : ) = Pr * Palr( :, sl:sl+sr-1 )'

inv( L ) * Pa

Shernman-Morrison-Woodbury

Xa = [ Xl; Xr; ]

Pa( 0:nl-1, : ) = Pl * Palr( :, 0:sl-1 )'

Pa( nl:n-1, : ) = Pr * Palr( :, sl:sl+sr-1 )'

xl = Vlt * Pa( 0:nl-1, : )

xr = Vrt * Pa( nl:n-1, : )

b = [ Crl' * xr; Crl * xl; ]

b = inv( Z ) * b

Pa( 0:nl-1, : ) -= Ul * b( 0:sl-1, : )

Pa( nl:n-1, : ) -= Ur * b( sl:sl+sr-1, : )

end if ( DO_INVERSE )

end if ( do_ulv_factorization )

Parameters
Pan-by-s
Palrs-by-(sl+sr)
Plnl-by-sl
Prnr-by-sr
template<typename T >
void hmlp::gofmm::Factor< T >::ULVBackward ( )
inline

end ULVForward()

Copy Bp (subview of parent's B) to Bc.

Bf -= Ufc * Bc, where Ufc is Ztr.

Lff^{-1} * P * Bf, where Lff is the lower-triangular part of Ztl.

Create a temporary buffer for projection Q2 * Bf + Q1 * Bc.

Copy A back to B.

template<typename T >
void hmlp::gofmm::Factor< T >::ULVForward ( )
inline

changeBasis()

For internal nodes, B has been initialized by children.

B = Q' * B

P * Bf

Lff^{-1} * P * Bf, where Lff is the lower-triangular part of Ztl.

Bc -= Lcf * Bf, where Lcf is Zbl.

Copy Bc to Bp (subview of parent's B).

Member Data Documentation

template<typename T >
Data<T> hmlp::gofmm::Factor< T >::B

Temporary buffer for the solve.

template<typename T >
View<T> hmlp::gofmm::Factor< T >::bview

A correspinding view of the right hand side of this node.

template<typename T >
Data<T> hmlp::gofmm::Factor< T >::Crl

sr-by-sl and sl-by-sr, skeleton row and column basis.

template<typename T >
vector<int> hmlp::gofmm::Factor< T >::ipiv

Partial pivoting order (used in GETRF).

template<typename T >
bool hmlp::gofmm::Factor< T >::isleaf = false

end ULVBackward()

template<typename T >
Data<T> hmlp::gofmm::Factor< T >::Q

Q, (sl+sr)-by-s (ULV)

template<typename T >
vector<T> hmlp::gofmm::Factor< T >::tau

tau, sl+sr (used in xgeqrf( U ) of ULV)

template<typename T >
Data<T> hmlp::gofmm::Factor< T >::U

n-by-s (SMW) or (sl+sr)-by-s (ULV)

template<typename T >
Data<T>* hmlp::gofmm::Factor< T >::Ul = NULL

Pointers to children's factors

template<typename T >
Data<T> hmlp::gofmm::Factor< T >::Z

Reduced system Z = [ I VU if ( HODLR || p-HSS ) VU I ]

The documentation for this class was generated from the following file: