Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

A Preconditioned ELMRES Implementation

Mehdi Delkhosh*, Hossein Zareamoghaddam

Department of Mathematics, Islamic Azad University, Bardaskan Branch, Bardaskan, Iran

Abstract: In this paper we review the ELMentary RESidual(ELMRES) algorithm for solving linear system of equations. ELMRES is a krylov subspace method which uses the Hessenberg transformation as the projection technique for reducing the dimension of original matrix A. We apply some preconditioned techniques for this algorithm. At the end of this paper, some numerical examples have been shown to compare the preconditioned ELMRES with the original version.

Keywords: ELMRES, preconditioned technique, Hessenberg algorithm, least square problems

Received September 19, 2013; Revised October 10, 2013; Accepted October 11, 2013

Citation: Mehdi Delkhosh, Hossein Zareamoghaddam, A Preconditioned ELMRES Implementation. Applied Mathematics and Physics, 1 (4). 90-93. January 2013. doi:10.12691/amp-1-4-1

1. Introduction

Many applications require the solution of several sparse systems of linear equations

[picture] | (1)

with the coefficient matrix , the right hand side vector and the unknown solution vector .

There are several different iterative algorithms for computing the solution of (1). Among them, krylov subspace methods, like algorithms from [1,3,5,6], are more popular solvers for this sort of equations. The krylov subspace is defined as

which is a practical subspace for modification of new approximations with where is the initial guess. ELMRES was proposed by G. Howell and D. Stephens [3] in 2000. The implementation of ELMRES is approximately similar to GMRES so that in both methods the original problem (1) is transferred to an upper Hessenberg least square problem with dimension which whilst GMRES uses the Arnoldi orthogonalization algorithm for reduction and ELMRES uses the Hessenberg decomposition algorithm. The construction of this paper is as follows: In section 2, the ELMRES is discussed. In section 3, the left and right preconditioner methods are described shortly and some popular applicable matrices for these methods which are also practical for ELMRES are shown. In the next section, the proposed preconditioned matrices are applied and then they are tested by some numerical examples.

2. Elmres

Here the ELMRES algorithm is described briefly. In ELMRES method a basis constructs for the krylov subspace by the Hessenberg algorithm. Suppose . Now, the procedure for extending the dimension of the subspace is shown in the following algorithm [3].

2.1. Algorithm 1: Hessenberg Decomposition Algorithm

1. vector and set and .

2. for

1. 

2. 

End

3. 

In the algorithm 1, it is shown that the step of the for loop zeros the entry of where . At the end of algorithm, the entry of becomes . In this case, . If the partial pivoting is employed, the relation

[picture] | (2)

is concluded,(see [3]).

An elementary similarity transformation is of the form

[picture] | (3)

where is a column vector with zeros as its first entries and is a vector with its only nonzero entry in the position.

Without pivoting condition, reduction by elementary similarity transformations to upper hessenberg form is accomplished by

[picture] | (4)

which form the structures of s and upper hessenberg matrix we have

By definition of and the following relation is obtained

[picture] | (5)

By using this important relation, we reach to the reduced problem

The approximate solution is where .

Wilkinson [8] suggested Hessenberg reduction with implicit pivoting avoids the breakdown in decomposition process. Here, the ELMRES with implicit pivoting [3] is shown.

2.2. Algorithm 2: ELMRES with Implicit Pivoting

1. Choose , set

set so that .

2. For , until satisfied do

,

For ,

,

End

,

For do

,

,

End

set so that .

,

.

End

Choose to minimize .

3. From the approximate solution .

For ,

,

End

For more information about ELMRES and its properties see [3].

3. Preconditioned ELMRES

The structure of GMRES is approximately similar to ELMRES. So, some prediction GMRES techniques may be useful for ELMRES. Here, GMRES with right preconditioners are shown and some suitable matrices for preconditioned ELMRES are suggested.

Let is a preconditioned matrix. In left preconditioned GMRES, the original equation is replaced with and the orthogonalization procedure is run so that a normalized basis vectors is obtained for the preconditioned krylov subspace

by the Arnoldi algorithm. So, we have to apply GMRES algorithm just for the new linear system of equations.

Furthermore, the right preconditioned GMRES algorithm is based on solving

[picture] | (6)

As the right preconditioned GMRES is more practical, its algorithm is written below [6].

2.3. Algorithm 3: Right Preconditioned GMRES

1. Choose , set.

2. For

,

For

do , ..,

End

,

If set and goto 3,

End

3. and .

From the above algorithm, the vector is not computed explicitly and the Arnoldi process generates a basis vector set for the preconditioned subspace

.

In this case, the residual norm is now relative to the initial system (1).

Gauss-Seidel and SOR are two popular classical iterative methods for solving (1) while using the matrices regard to the structure of these methods as some preconditioners are popular techniques for GMRES. Now, we apply the preconditioned matrices and obtained from Gauss-Seidel and SOR respectively. Suppose where , and are the elements lower than the diagonal, the diagonal elements and the elements upper than the diagonal of matrix respectively. So, and are defined as follows [6],

[picture] | (7)

4. Numerical Tests

The In this section, some well-known numerical examples are applied to test the effect of preconditioned techniques on the convergence speed of ELMRES. For simplicity, is chosen as the initial guess in these experiments. These algorithms are implemented in Matlab 7.3 on a Pentium 4 PC with 1 GB of RAM. The stopping criterion is used for all implementations.

Example 1: For construction of linear system of equations (1), Let be an even integer and denote by and , respectively, the identity and zero matrices. Define also the matrices and as in

Finally, construct the non-symmetric matrix as in

The matrix is obtained by first discretizing the Poisson equation

for

with Neumann boundary conditions

on a uniform grid of mesh size via central differences, and then by taking the unknowns in the red-black ordering. This problem was also considered by Saberi Najafi and Zareamoghaddam in [7] for testing another GMRES implementation. Note that is singular with a 1D null space spanned by the vector .

In our numerical experiments, for the first exam we took which the corresponding square matrix is in order . Table1shows the numerical results of different ELMRES implementations applied for the linear problem with order .

Table 1. Numerical results of example1

Table 2. Numerical results of example2

Example 2: There are many different numerical examples for system of linear equations which among them, "Regularization Tools" of Prof. Hansen [2] is one popular package for ill-posed linear system of equations. In this example, the main source code of one discrete image deblurring problem is selected from this package [2]. The Matlab code "blure" with detailed parameters , and , i.e. is used to generate the square matrix with the right hand side vector . This problem has been contaminated by blur and noise. Numerical results of this test have been illustrated in Table 2.

5. Conclusion

Elementary residual method is rather a new krylov subspace method for solving linear system of equations. In this paper, some right preconditioned matrices have been tested for ELMRES to solve different linear system of equations and the results show that the convergence of ELMRES has also been influenced by some appropriate preconditioning matrices.

Acknowledgement

Hereby, the authors want to thank of Islamic Azad University, Bardaskan Branch because of the financial support.

References

[1]   | Freund R., Nachtigal N., QMR: A Quasi-Minimal Residual Method for Non-Hermitian Linear Systems, Numer. Math. 60(1991) 315-339.
[2]   | Hansen P. C., Regularization Tools Version 4.0 for Matlab 7.3, Numerical Algorithms, 46 (2007) 189-194.
[3]   | Howell G., Stephens D., ELMRES: an oblique projection solver for sparse systems of linear equations, technical report, Florida Institute of Technology, 2000.
[4]   | Lewis B., Reichel L., Arnoldi-Tikhonov regularization methods, J. Comput. Appl. Math., 226 (2009) 92-102.
[5]   | Paige C. C., Saunders M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8 (1982) 43-71.
[6]   | Saad Y., Iterative method for sparse linear systems. PWS publishing company, a division of international Thomson publishing Inc, U.S.A, 1996.
[7]   | Saberi Najafi H., Zareamoghaddam H., A new computational GMRES method, Appl. Math. Comput. 2 (2008) 527-534.
[8]   | Wilkinson J. H., the Algebraic Eigenvalue Problem. Clarendon Press, Oxford, England, 1965.