258
MATRIX DECOMPOSITION AND MATRIX SOLVERS IN PHOTOGRAMMETRY
Cheng Chunquan ab ’* Deng Kazhong b Zhang Jixian a YanQin 3
“Chinese Academy of Surveying and Mapping, 16 Beitaiping Road, Beijing, China, 10039-cspring@casm.ac.cn
b School of Environmental and Spatial Informatics,China University of mining & Technology,xuzhou,jiangsu,221008
KEY WORDS: Matrix decomposition Matrix solver Matrix computation Photogrammetry
ABSTRACT:
A matrix decomposition is a factorization of a matrix into the product of simpler matrices. It is a effective method to solve large
linear systems through matrix decomposition. Firstly we will give introduction of matrix decompositions into numerical linear
algebra revolutionized matrix computations, outlining the most widely used decompositions: the Cholesky decomposition, the LU
decomposition, the QR decomposition, the spectral decomposition, the Schur decomposition, and the singular value decomposition.
Then we will introduce several famous matrix computation libraries and large sparse matrix solvers, including C++/Cooperware
Matrix, C++/ Blitz, C/meschach, unsymmetric multifrontal sparse LU factorization package (C/UMFPACK), INTEL PARDISO,
GRUS SPARSE SOLVER(GSS).At last a block adjustment programme as example is given to show the convenience of matrix
computation with meschach library and sparse matrix solver.
1. INTRODUCTION
The numerical solution of large sparse linear systems lies at the
heart of many large-scale scientific and engineering
computations, in company with Partial Differential
Equations ,integral equations, eigenvalue, optimization and
others becoming the keys to numerical solution. Today,
systems of equations with more than one million unknowns
need to be solved. The World’ s Largest Matrix
Computation,Google's PageRank, is an eigenvector of a matrix
of order 2.7 billion.To solve such large systems in a reasonable
time requires the use of powerful parallel computers. To date,
only limited software for such systems has been generally
available. Matrix computations are also widely used in
coordinate translation, adjustment and image procession in
photogrammetry. matrix order number in block adjustment
may exceed ten thousands, time cost and EMS memory
capability are Limitations to computation by dense matrix
method, so the numerical solution of large sparse linear
systems together with sensor, image mathematical model,
Image Matching and other key techniques also consist the
emphases of today’s photogrammetry techniques.
the system one has first to solve the system Ly=b and then the
system Ux=y.
Proposition 2 : If and only if det(A(l:k,l:k))^0 for (k=l:n-
l),then AGR” has an LU factorization. If the LU
factorization exists and A is regular, then the LU factorization
is unique and det(A)=Un u nn .
Proposition 3. If AGR nxn and det(A) ¿0, then there exists a
permutation matrix PGR nxn , such that all the principal minors
of PA are nonzero, and consequently, there exists the LDU
factorization .A=L(DU)=LU is Doolittle - Factorization,
A=(LD)U=L Crout-Factorization. When A is Real Symmetric
Matric and det(a)>0, A=LDU=LD 2 U=(LD)(LD) T =GG T where
G is a triangular matrix, is to be cholesky- Factorization.
Large sparse matrix solution method with LU-Factorization
usually have the following steps:
1. find the permute matrix: B = PAP T
2. Matrix decomposition B = LU
3. Solve the vector y: Ly = Pb
4. Solve the vector z Uz = y
5. Get the value X = P T z
2.2 QR-Factorization
2.MATRIXDECOMPOSITION
A matrix decomposition is a factorization of a matrix into the
product of simpler matrices, usually factorize a matrix into
several triangular matrix . the most widely used decomposition
methods include Triangular Factorization, QR Factorization
and Singular Value decomposition.
2.1 Gauss Transformation and LU-Factorization
Under certain conditions the system matrix A of the equation
Ax=b can be expressed in the form of a product of a unit lower
triangular matrix L with units on the main diagonal and an
upper triangular matrix U,and as the result, one has to solve
two systems with triangular matrices.
Proposition 1: If A£R nxn , A=LU, where L is unit lower
triangular, U is regular upper triangular, we call A can be LU-
Factorized. If A=LDU,where D=diag(a 1 ,a 2 ,...a n ). The solution
of x in Ax=b is the solution x in LUx=b, so for the solution of
Every real matrix A has a QR decomposition, A = QR, in
which Q has or-thonormal columns and R is upper triangular. If
A is m-by-n, with m > n,. then Q is m-by-n and R is n-by-n. A
QR decomposition can be computed with the Gram-Schmidt
procedure, or using Householder reflectors and Givens rotator.
It has the following Propositions:
If A<=R mxn (m>n), there exist the Householder matrices Hi
such that
Q =
R =
i Hr-
....H n ,kui.m > n,
K
...H n ,,kuim = n;
K-
....H x A,kui.m > n,
...H n ,A,kuim = n:
And A=QR where Q£R mxm is orthogonal and RGR mxn is
upper triangular.
The Householder reflection is effective for intruducing zeros if
there are "many" components to be annihilated. If it is
necessary to nullify only one component, sometimes a couple
of components, then usually the Givens method is used.
