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.