(Sparse) Linear solvers explanation1.pdf

its a pdf explaining Linear solvers for sparse systems

1. (Sparse) Linear Solvers
AB ABA
x =
B A
x =
B

2. Why? Why?
Many geometry processing applications boil down to:
solve
oneormorelinearsystems
solve
 one
 or
 more
 linear
 systems
Parameterization
Editing
Reconstruction Fairing Morphing

3. Don
’tyoujustinvert
A
?
•M
at
rix n
ot
 a
lw
ays
 inv
e
r
t
ib
le
Dont
 you
 just
 invert
 A
?
atotaaysetbe
–Not square
Ax b
Axb
Overdetermined
Underdetermined
–Singular
Over
 determined
Under
 determined
•Almost singular

4. Don
’tyoujustinvert
A
?
Dont
 you
 just
 invert
 A
?
•Even if invertible
V
i
O(
3
)
–
V
eryexpens
ive 
O(
n
3
)
–Usually n= number of vertices/faces

5. Problemdefinition
•Input
Problem
 definition
–Matrix A
mxn
–Vector B
mx1
•Output
–Vector x
nx1
–
Such that Ax = B
•
Smalltimeandmemorycomplexity
•
Small
 time
 and
 memory
 complexity
•Use additional information on the 
p
roblem 
p

6. Propertiesof
linear
systemsforDGP
Properties
 of
 linear
 systems
 for
 DGP
•S
p
arse 
A
p–Equations depend on 
graph neighborhood
–Equations on vertices 
Æ
7
Æ
7
non‐zeros per 
row on average
–Number of non zero 
elements O
(
n
)
n= 1002
(
)
N
on zeros = 7002

7. Propertiesof
linear
systemsforDGP
Properties
 of
 linear
 systems
 for
 DGP
•S
y
mmetric 
p
ositive definite 
(p
ositive 
y
p(p
eigenvalues)
–Many times Ais the Laplacianmatrix –Laplaciansystems are usually SPD
•Aremains, bchanges –many right hand sides
–Interactive applications –Mesh geometry –same matrix for X, Y, Z

8. Linearsolverszoo Linear
 solvers
 zoo
 
•A is square and regular •Indirect solvers –iterative
–
Jacob
i
Jacob
–Gauss‐Seidel
–Conjugate gradient
•Direct solvers –factorization
–LU –
QRQR
–Cholesky
•
Multigridsolvers
•
Multigrid
 solvers
 
8

9. Jacobiiterativesolver Jacobi
 iterative
 solver
•
If
allvariablesareknownbutone,itsvalue
If
 all
 variables
 are
 known
 but
 one,
 its
 value
 
is easy to find
•
Idea
:
•
Idea
:
–Guess initial values –
Repeatuntilconvergence Repeat
 until
 convergence
•Compute the value of one variable assuming all 
others are known
•Repeat for all variables
9

10. Jacobiiterative
solver
Jacobi
 iterative
 solver
•
Let
x
*
betheexactsolution
of
Ax
*
=
b
Let
 x
be
 the
 exact
 solution
 of
Ax
b
•Jacobi method
–Set 
–While not converged
Values from 
previousiteration
•For i= 1to n
previous
 iteration
10

11. Jacobi iterative solver
Pros
Si ltil t
•
Si
mp
le 
t
o 
imp
lemen
t
–No need for sparse data structure
•Low memory consumption O(n) •
Takes
advantageofsparse
structure
Takes
 advantage
 of
 sparse
 structure
bll li d
•Can 
b
e para
ll
e
li
ze
d
11

12. Jacobi iterative solver
Cons
•Guaranteed conver
g
ence for strictl
y
 dia
g
onall
y
 
gygy
dominant matrices
–The Laplacianis almostsuch a matrix
•
Converges
SLOWLY
•
Converges
 SLOWLY
–Smoothens the error
–Once the error is smooth, slow convergence
•Doesn’t take advantage of
–
Same 
A
, different b ,
–SPD matrix
12

13. Directsolvers
‐
factorization
Direct
 solvers
 
factorization
•
IfAisdiagonal/triangularthesystemiseasytosolve If
 A
 is
 diagonal/triangular
 the
 system
 is
 easy
 to
 solve
•
Idea:
•
Idea:
 
–Factor Ausing “simple”matrices 
x
1
–Solve using keasy systems
13

14. Directsolvers
‐
factorization
Direct
 solvers
 
factorization
•
Factoring
harderthansolving
•
Factoring
 harder
 than
 solving
•Added benefit –multiple right hand sides
–
Factor
onlyonce!
Factor
 only
 once!
14

15. Solvingeasymatrices Solving
 easy
 matrices
Diagonal Diagonal
 
15

16. Solvingeasymatrices Solving
 easy
 matrices
Lowertriangular Lower
 triangular
•Forward substitution •
Startfrom
x
•
Start
 from
 x
1
16

17. Solvingeasymatrices Solving
 easy
 matrices
Uppertriangular Upper
 triangular
•Backward substitution •
Startfrom
x
•
Start
 from
 x
n
17

18. LUfactorization LU
 factorization
•
A
= L
UU
–Llower triangular
–Uupper triangular •Exists for any non‐singular square matrix •Solve using Lx
1
=band Ux=x
1
18

19. QRfactorization QR
 factorization
•
A
=
QR
A

QR
–Qorthogonal ÆQ
T
= Q
-1
–
Rupper triangular
•Exists for any matrix •Solve using Rx =Q
T
b
19

20. Choleskyfactorization Cholesky
 factorization
•A = LL
T
–Llower triangular
•
Existsforsquaresymmetricpositivedefinite Exists
 for
 square
 symmetric
 positive
 definite
 
matrices
•Solve using Lx
1
=band L
T
x=x
1
20

21. Directsolvers
–
sparsefactors?
Direct
 solvers
 
sparse
 factors?
•
Usuallyfactorsare
not
sparseevenif
A
is
Usually
 factors
 are
 not
sparse
, 
even
 if
 A
is
 
sparse
Sparse matrix
Cholesk facto
21
Sparse

matrix
Cholesk
y
facto
r

22. Sparsedirectsolvers Sparse
 direct
 solvers
•
Reordervariables/equationssofactorsaresparse Reorder
 variables/equations
 so
 factors
 are
 sparse
•For example
Bandwidthis
preserved
Æ
Reordertominimize
–
Bandwidth
 is
 preserved
 Æ
Reorder
 to
 minimize
 
badnwidth
22
Sparse matrix
bounded bandwith
Cholesky factor

23. Sparsedirectsolvers Sparse
 direct
 solvers
•SPD matrices
–
Choleskyfactor sparsitypattern can be derived from 
matrix’sparsitypattern
•
Reordertominimizenewnonzeros(
fillin
)offactormatrix
Reorder
 to
 minimize
 new
 non
 zeros
 (
fill
 in
)
 of
 factor
 matrix
23
Sparse matrix - reorderedCholesky factor

24. SparseCholesky Sparse
 Cholesky
•Symbolic factorization
–
Can be reused for matrix with same sparsitystructure
•Even if values change!
OlfSPDi
•
O
n
ly 
f
or 
SPD
 matr
ices
•Reorderin
g
 is heuristic 
–
not alwa
y
s 
g
ives 
g
ood s
p
arsit
y
g
ygg
py
–High memory complexity if reordering was bad
•
BUT
•
BUT
–Works extremely well for Laplaciansystems
–Can solve systems up to n= 500K on a standard PC
24

25. Under
‐
determined
systems
Under
determined
 systems
•System is under‐constrained Ætoo many variables •
Solution
:addconstraintsbypinningvariables
•
Solution
:
 add
 constraints
 by
 pinning
 variables
–Add equations x
1
= c
1
,x
2
= c
2
, ... , x
k
= c
2
OrOr –Replace variables with constants in equations
•
Better
smallersystem
•
Better
 –
smaller
 system
25

26. Over
‐
determined
systems
Over
determined
 systems
•System is over‐constrained Ætoo many 
equations
•Unless equations are dependent, no solution 
exists
•Instead, minimize: 
26

27. Over
‐
determined
systems
Over
determined
 systems
•The minimizerof  •Is the solution of  •A
T
Ais symmetric positive definite
–
Canuse
Cholesky
Can
 use
 Cholesky
27

28. Singularsquarematrices Singular
 square
 matrices
•
Equivalenttounder
‐
determinedsystem
Equivalent
 to
 under
determined
 system
ddi
•A
dd
 constra
ints
–By changing variables to constants –
NOT by adding equations!
•Will make system not square •Much more expensive
28

29. Conclusions Conclusions
•Man
y
 linear solvers exist
y
•Best choice depends on A •DGP algorithms generate sparse SPD systems •Research shows sparse linear solvers are best for DGP •Sparse algs exist also for non‐square systems •
IfsolvinginMatlab
use
“
\
”
operator
•
If
 solving
 in
 Matlab
 –
use
 “
\
”
operator
29

30. References References
•“
EfficientLinearSystemSolversforMesh Efficient
 Linear
 System
 Solvers
 for
 Mesh
 
Processing”, Botschet al., 2005
30