259

Gram-Schmidt Orthonormalization Method:

Since orthonormal vectors are easier to work with, we need an

algorithm to change vectors aj,..., a k by linear combinations to

an orthonormal set. The Gram-Schmidt method produces

orthonormal vectors q k ... q k such that the span of q,... q, is the

same as the span of a,; : : : ; aj for 1 ,j, k. We do this by

iteratively subtracting o_ projections onto previous subspaces:

a’j = aj - (q T i aj)qi -...-(q^-^jjqj-l; where a’j is subsequently

discarded if it is 0, or normalized if it is not:

qj =a Vll a ’jll

If a b ...a k are linearly independent, we do not need to worry

about discarding any vectors, they will be linearly independent

and thus, a fortiori, nonzero.

We usually need to use QR factorisations to find the best

linear least squares solution to some data. Thus in order to

solve the (approximate) equations Ax approx= b, for x where A

is an m x n matrix (m>n) we really need to solve the

optimisation problem

2.3 sigular value decomposition, SVD

Singular value decomposition takes a rectangular matrix of

gene expression data (defined as A, where A is a n xp matrix)

in which the n rows represents the genes, and the p columns

represents the experimental conditions. The SVD theorem

states:

y^nxp_ jjnxn gnxp yT pxp

Where U T U = I nxp V T V = I pxp (i.e. U and V are orthogonal)

Where the columns of U are the left singular vectors [gene

coefficient vectors)-, S (the same dimensions as A) has singular

values and is diagonal (mode amplitudes)-, and V T has rows that

are the right singular vectors (expression level vectors). The

SVD represents an expansion of the original data in a

coordinate system where the covariance matrix is diagonal.

Every matrix has a singular value decomposition .SVD is a

kind of reliable but may cost ten more time than QR

decomposition. Calculating the SVD consists of finding the

eigenvalues and eigenvectors of AA T and A T A. The eigenvectors

of A T A make up the columns of V, the eigenvectors of AA T make

up the columns of U. Also, the singular values in S are square

roots of eigenvalues from AA T or A T A. The singular values are the

diagonal entries of the S matrix and are arranged in descending

order. The singular values are always real numbers. If the matrix

A is a real matrix, then U and V are also real.

SVD factorizations are usually used to find the best linear least

squares solution and compression to some data, that digital image

is transformed into singular value matrix that contains non-zero

singular values by singular value decomposition (SVD), the

image is compressed.

3.MATRIX LIBRARY

A matrix library is for performing matrix algebra calculations

in programs in easy and efficient manner for engineering &

scientific works. They ofen supports most of the matrix algebra

operations and enables programmers to use matrix object just

like other built-in data types in their programs. It supports

arithmetic operations, sub-matrix operations, inversion, various

matrix decompositions, solution of simultaneous linear

equations, eigen value and eigen vector problems, and much

more.

3.1 meschach:

Library for performing operations on matrices and vectors

Meschach is a library of routines written in C for matrix

computations. These include operations for basic numerical

linear algebra; routines for matrix factorisations; solving

systems of equations; solving least squares problems;

computing eigenvalues, eigenvectors and singular

values;sparse matrix computations including both direct and

iterative methods. This package makes use of the features of

the C programming language: data structures, dynamic

memory allocation and deallocation, pointers, functions as

parameters and objects. Meschach has a number of self-

contained data structures for matrices, vectors and other

mathematical objects.

Meschach has the virtue of compiling under Linux and most

other operating systems, and is openly available under

copyright, provided the customary acknowledgment is

observed and errors are reported. Meschach was designed to

solve systems of dense or sparse linear equations, compute

eigenvalues and eigenvectors, and solve least squares problems,

among other things. It provides nearly 400 functions for

doubles and complex numbers. Matrices can easily be sent to

files or to the standard output. Meschach computes Fast Fourier

Transforms, extracts columns and rows, and computes

eigenvalues of symmetric matrices. You can fill a matrix with

random ints and complexes. Meschach code is easily extensible,

if you happen to be doing computational work in C that needs

matrices, this is a highly useful library.

3.2 The CwMtx library for matrix, vector and quaternion

math

CwMtx is a library wrote in C++ that provides the matrix and

vector operations that are used extensively in engineering and

science problems. A special feature of this library is the

quaternion class which implements quaternion math.

Quaternions are very useful for attitude determination in 3D

space because they do not suffer from singularities.

Furthermore, successive rotations and transformations of

vectors can be accomplished by simple quaternion

multiplication. Attitude dynamics can be expressed in a very

compact form using quaternions.

3.3 Blitz

Blitz ++ is a C++ class library for scientific computing

which provides performance on par with Fortran 77/90. It uses

template techniques to achieve high performance. The current

versions provide dense arrays and vectors, random number

generators, and small vectors and matrices. Blitz++ is

distributed freely under an open source license, and

contributions to the library are welcomed. It is distributed

under the GNU GPL, and with it you can freely create objects.

It supports the KAI, Intel, gcc, Metroworks, and Cray 3.0.0.0

C++ compilers and provides an n-dimensional array class that

can contain integral, floating, complex, and well-behaved user-

defined types. Its constructor is more complex that the CwMtx

constructor.

4.DIRECT SOLVERS FOR LARGE SPARSE MATRICES

The technique to solve sparse matrix including direct Factor

and iterative method. UMFPACK, superLU, intel

PARDISO,GSS are all famous direct solvers for sparse

matrices.