Applied Mathematics, 2011, 2, 1446-1447
doi:10.4236/am.2011.212205 Published Online December 2011 (http://www.SciRP.org/journal/am)
Extension of Range of MINRES-CN Algorithm
Mojtaba Ghasemi Kamalvand
Department of Mathematics, Lorestan University, Khorramabad, Iran
Received January 20, 2011; revised May 10, 2011; accepted May 18, 2011
Abstract
MINRES-CN is an iterative method for solving systems of linear equations with conjugate-normal coeffi-
cient matrices whose conspectra are located on algebraic curves of a low degree. This method was proposed
in a previous publication of author and KH. D. Ikramov. In this paper, the range of applicability of MIN-
RES-CN is extended in new direction. These are conjugate normal matrices that are low rank perturbations
of Symmetric matrices. Examples are given that demonstrate a higher efficiency of MINRES-CN for this
class of systems compared to the well-known algorithm GMRES.
Keywords: Conjugate-Normal Matrices, MINRES-CN Algorithm, MINRES-CN2 Algorithm
1. Introduction and Preliminaries
Suppo se that one n eeds to so lve th e syste m of linear equ-
ations
A
xb (1)
with a conjugate-normal n × n-matrix A. In the context of
this paper, conjug a te-normality means that
**
A
AAA (2)
A particular example of conjugate-normal matrices are
symmetric matrices.
The method proposed in [1] is a minimum residual
algorithm for the subspaces, which are the finite seg-
ments of the sequence
**
,, ,,,,,
TT
x AxAxAAx AA x AA x AAAx,
T
(3)
Unlike GMRES, this method, called MINRES-CN, is
described by a recursion whose (fixed) length depends
on the degree m of Γ (the conspectrum (you can see defi-
nition of conspectrum in [2]) of A belongs to an alge-
braic curve Γ of a low degree)). For instance, the length
of the recursion is six in the case m = 2, which is given
the most attention in [1].
2. Extension of Range
In this section, the range of applicability of MINRES-CN
is extended in new direction.
We examine the behavior of MINRES-CN for new
class of matrices A that can be considered as low rank
perturbations of Sym metric matrices.
Let us first recall that any square complex matrix A
can be uniquely represented in the form (see [3])
,,
T
A
SKS SKK (4)
We consider the class of conjugate-normal matrices A
distinguished by the condition,
1
2
k
krankK   (5)
where n is the order of A. The conspectrum of such a
matrix belongs to the union of the real axis and (at most)
k lines that are parallel to the imaginary axis, i.e., to a
degenerate algebraic curve whose degree does not ex-
ceed k + 1. Hence, MINRES-CN is applicable to matri-
ces of this type.
3. Numerical Results
Therefore, we can apply MINRES-CN to solving sys-
tems with conjugate normal coefficient matrices satisfy-
ing conditions (4) and (5).
The efficiency of the method is illustrated by several
examples where band systems were solved. The perfor-
mance of MINRES-CN2 (which is a specialization of
MINRES-CN for conjugate normal matrices whose con-
spectra belong to a second-degree curve) in these exam-
ples is compared with that of the Matlab library program
implementing GM RES.
In examples, we used the Matlab library function
gmres for GMRES and a specially designed Matlab pro-
cedure for MINRES-CN2. The same stopping criterion

M. G. KAMALVAND 1447
was used for both methods; namely,
2
r

 (6)
where r is the current residual, while a positive scalar
should be given by the user. For the example under dis-
cussion, we set .

8
10  
In all of our experiments, the order of systems was
2000. The right hand sides were generated as pseudo-
random vectors with components distributed uniformly
on (0, 1). The calculations were performed on a 2 Duo
E630 OEM 1.86 GHz PC with core memory of 1024 Mb.
Example 3.1. Suppose that, where
for i and
1, 11,, 1nnnn nn (where A = S +
K and ), another entries of matrix A are zero.
The conspectrum is located on the coordinate axes; i.e., it
belong to the second-degree curve,
( ),
ijn n
Aa


2,n
11a
[10,14],
ij
a
,nn
aa
rankK
1, 2,,
11,a0,
2
0xy  (7)
It follows that a system with the matrix A can be proc-
essed by MINRES-C N 2.
MINRES-CN2 converges faster than GMRES (8 itera-
tion steps and t = 0.02 s against 11 steps and t = 0.09 s).
Example 3.2. Suppose that where
for i and
1, 11,, 1nn (where A = S
+ K and ), another entries of matrix A are
zero. The conspectrum is located on the real axis and the
line x = 2; i.e., it belong to the second-degree curve,
(),
ijn n
Aa


2,n
, 11
nn
a


[10, 14],
ij
a
,nn
aa
rank
1, 2,,
, 11
nn
a

2
12
K
( 12)0.xy


It follows that a system with the matrix A can be proc-
essed by MINRES-C N 2.
MINRES-CN2 needs 10 steps and t = 0.02 s, while
GMRES requires 12 steps and the time 0.09 s.
Example 3.3. Suppose that where ( ),
ijn n
Aa


[40,45],
ij
a

for 1,2,,i4,n


4 4,
41,a


3 ,
43,n n a
and
1, 3n n , 141 nn
43,
nn
aa


(where
A
SK

 and ), another entries of
matrix A are zero. The conspectrum is located on the
coordinate axes; i.e., it belongs to the second-degree
curve (7). It follows that a system with the matrix A can
be processed by MINRES-CN2. 7 iteration steps and t =
0.02 s for MINRES-CN2 against 12 steps and t = 0.08 s
for GMRES.
4Krank
4. References
[1] M. G. Kamalvand and Kh. D. Ikramov, “A Method of the
Congruent Type for Linear Systems with Conjugate-
Normal Coefficient Matrices,” Computational Mathe-
matics and Mathematical Physics, Vol. 49, No. 2, 2009,
pp. 203-216. doi:10.1134/S0965542509020018
[2] H. Fassbender and Kh. D. Ikramov, “Some Observations
on the Youla Form and Conjugate-Normal Matrices,”
Linear Algebra and Its Applications, Vol. 422, No. 1,
2007, pp. 29-38. doi:10.1016/j.laa.2006.09.004
[3] R. A. Horn and C. R. Johnson, “Matrix Analysis,” Cam-
bridge University Press, Cambridge, 1985.