A gene aliza ion o he op imal diagonal
app oxima e in e se p econdi ione I
Luis Gonz´alez∗, An onio Su´a ez, Edua do Rod ´ıguez
Depa men o Ma hema ics, Uni e si y o Las Palmas de G an Cana ia,
35017 Las Palmas de G an Cana ia, Spain
Abs ac
The classical op imal (in he F obenius sense) diagonal p econdi ione o
la ge spa se linea sys ems Ax =bis gene alized and imp o ed. The new
p oposed app oxima e in e se p econdi ione Nis based on he minimiza ion
o he F obenius no m o he esidual ma ix AM −I, whe e M uns o e
a ce ain linea subspace o n×n eal ma ices, de ined by a p esc ibed
spa si y pa e n. The numbe o nonze o en ies o he n×np econdi ioning
ma ix Nis less han o equal o 2n, and no hem a e selec ed as he
op imal posi ions in each o he ncolumns o ma ix N. All heo e ical esul s
a e jus i ied in de ail. In pa icula , he compa ison be ween he p oposed
p econdi ione Nand he op imal diagonal one is heo e ically analyzed.
Finally, nume ical expe imen s epo ed con i m he heo y and illus a e
ha ou gene aliza ion o he op imal diagonal p econdi ione imp o es (in
gene al) i s e iciency, when hey do no coincide.
Keywo ds: App oxima e in e se p econdi ione , F obenius no m
minimiza ion, Diagonal p econdi ione
1. In oduc ion
The disc e iza ion o many di e en PDEs (modeling physical p oblems)
by any adequa e nume ical me hod ( ini e di e ences, ini e elemen s, ini e
olumes, meshless, e c.), gene ally leads o a la ge linea sys em
ISho unning i le: A gene aliza ion o he op imal diagonal p econdi ione
∗Co esponding au ho .
Email add ess: [email p o ec ed] (Luis Gonz´alez)
P ep in submi ed o Compu e s &Ma hema ics wi h Applica ions Sep embe 10, 2013
Ax =b, A ∈Rn×n, x, b ∈Rn×1(1.1)
in which he ma ix Ais nonsingula and spa se.
The solu ion o hese linea sys ems is usually pe o med by i e a i e
me hods based on K ylo subspaces (see, e.g., [1, 2, 3, 4]). To imp o e he
con e gence o hese K ylo me hods, sys em (1.1) can be p econdi ioned
wi h an adequa e p econdi ioning ma ix N, ans o ming i in o any o he
equi alen p oblems
NAx =Nb, (1.2)
ANy =b, x =Ny, (1.3)
ha is, he le and igh p econdi ioned sys ems, espec i ely. In his pape ,
we add ess only he case o igh -sided p econdi ione s (1.3), bu analogous
esul s can be ob ained o he le -sided p econdi ione s (1.2). The s udy
o p econdi ioning s a egies o la ge linea sys ems is a p esen one o he
mos ele an esea ch a eas in Nume ical Linea Algeb a. In [5], we can ind
a e y comple e su ey abou his ques ion. The p econdi ioning o sys em
(1.1) is pe o med in o de o ob ain a p econdi ioned ma ix AN as close as
possible o he iden i y in some sense, and he p econdi ione Nis called an
app oxima e in e se o A.
The di e en s a egies o cons uc app oxima e in e se p econdi ione s
can be g ouped in o h ee ca ego ies [6]: app oxima e in e se me hods based
on F obenius no m minimiza ion, ac o ized spa se app oxima e in e ses (see,
e.g., [7, 8, 9] and he e e ences he ein), and p econdi ioning me hods con-
sis ing o an incomple e ac o iza ion ollowed by an app oxima e in e sion
o he incomple e ac o s.
The idea o using F obenius no m minimiza ion o p econdi ioning pu -
poses was i s desc ibed in [10], and o he ea ly wo ks can be ound in
[11, 12, 13]. Some pos e io app oaches in his sense can be ound, o in-
s ance, in [14, 15, 16, 17, 18, 19] and in he e e ences he ein.
In some cases, he F obenius no m based p econdi ione s a e pa ame ized
by p esc ibed spa si y pa e ns. O he wise, among he F obenius no m min-
imiza ion p econdi ione s no ex ac ed om spa se ma ix subspaces, le
us men ion he e he p econdi ione s o s uc u ed ma ices ob ained by o -
hogonal p ojec ions on o uni a y ma ix algeb as (like, o ins ance, ci cu-
lan p econdi ione s o Toepli z ma ices); see, e.g., [20, 21, 22] and he
e e ences he ein.
2
In [23, 24], he sea ch o F obenius no m based app oxima e in e ses wi h
a p esc ibed spa si y pa e n is gene alized by conside ing a mo e gene al
case o linea pa ame iza ion whe e p econdi ione s belong o an a bi a y
ma ix subspace So Rn×n. This p ocedu e leads o a na u al gene aliza ion
o he classical Moo e-Pen ose in e se, he so-called S-Moo e-Pen ose in e se
in oduced in [25].
The closeness o he p econdi ioned ma ix AN o he iden i y may be
measu ed by using a sui able ma ix no m like, o ins ance, he F obenius
no m k·kF. In his way, he p oblem o ob aining he bes p econdi ione N
(wi h espec o he F obenius no m) o sys em (1.1) in he subspace So
Rn×nis educed o he minimiza ion p oblem
min
M∈S kAM −IkF=kAN −IkF(1.4)
and he solu ion N o p oblem (1.4) will be e e ed o as he “op imal”
p econdi ione o sys em (1.1) o e he subspace S.
I is impo an o highligh ha , h oughou his pape , he e m “op-
imal” means ha he app oxima e in e se Nis he ma ix ha minimizes
he F obenius no m on AN −Io e a ce ain subspace So Rn×n, bu he
p econdi ione Nis no necessa ily op imal in any o he sense o he wo d.
Le us b ie ly desc ibe he basic idea o his wo k. Ou s a ing poin is
he well-known op imal diagonal p econdi ione ; see, e.g., [4]. This is exac ly
he solu ion D o p oblem (1.4) o he subspace o all n×ndiagonal ma ices,
and i is o en used as a simple p econdi ione o spa se linea sys ems.
Some imes, he p econdi ione Dis e icien and i leads o as con e -
gence. Fo ins ance, his is usually he case when ma ix Ais symme ic
posi i e de ini e [2]. Howe e , in o he cases, he diagonal p econdi ione D
is no e ec i e enough o con e gence.
Then, we imp o e Din he ollowing na u al way. Since, ob iously, he
diagonal ma ix Dhas one and only one nonze o elemen pe column, his
sugges s he idea o conside ing he bes app oxima e in e se (in he F obe-
nius sense) o ma ix Aamong all he n×nma ices ha ha e exac ly one
nonze o elemen pe column. Call each o such nonze o elemen s he op imal
ow posi ion o en y o i s co esponding column. Then, ou p oposed p e-
condi ione Nwill con ain he ndiagonal en ies and hose op imal en ies
pe column which do no coincide wi h he diagonal ones. Finally, Nwill be
exac ly he solu ion o p oblem (1.4) o he subspace S ⊂ Rn×n, de ined by
he abo e desc ibed spa si y pa e n.
3
Ob iously, he so de ined app oxima e in e se No ma ix Agene alizes
D, and i has a leas nnonze o en ies ( he diagonal ones), and a mos 2n
nonze o en ies.
Mo eo e , he p econdi ioning ma ix Nhas ano he ad an age, com-
pa ed wi h he classical diagonal app oxima e in e se D. Namely, he ei e -
a ion o he p econdi ioning echnique wi h he op imal diagonal app oxima e
in e se makes no sense. On he con a y, when using ou new p econdi ione
N, he well-known mul is ep p econdi ioning s a egy (see, e.g., [15, 26]) no
only makes sense, bu as we shall p o e, each s ep o his ei e a ed p econ-
di ioning s a egy s ic ly educes he F obenius no m o he esidual ma ix,
whene e he p econdi ione Nob ained in he p e ious s ep is no diagonal.
We p opose a simple, na u al gene aliza ion o he op imal diagonal p e-
condi ione , which imp o es i (in he sense o Eq. (1.4)). Theo e ical esul s
will be jus i ied in de ail and illus a ed wi h some nume ical expe imen s.
In addi ion, he p oposed p econdi ione is also compa ed wi h he AINV
app oxima e in e se p econdi ione [6].
This pape has been o ganized as ollows. In Sec ion 2, we ecall explici
exp essions o bo h he solu ion N o p oblem (1.4) and i s co espond-
ing minimum F obenius no m kAN −IkF, alid o any ma ix subspace
S ⊂ Rn×n. Nex , in Sec ion 3, we de i e explici exp essions o he p o-
posed p econdi ione Nand o kAN −IkF. Nume ical expe imen s a e p e-
sen ed in Sec ion 4. Finally, Sec ion 5 closes he pape wi h some concluding
ema ks.
2. A p elimina y lemma
Now, we p esen a p elimina y lemma equi ed o make his pape sel -
con ained.
Taking ad an age o he p ehilbe ian cha ac e o he ma ix F obenius
no m, he solu ion N o p oblem (1.4) can be di ec ly ob ained using he
o hogonal p ojec ion heo em. He e and in he ollowing, o hogonali y is
wi h espec o he F obenius inne p oduc h·,·iF. Mo e p ecisely, he ma ix
p oduc AN is he o hogonal p ojec ion o he iden i y on o he subspace
AS. Consequen ly, an explici o mula o ma ix Ncan be ob ained by
exp essing he o hogonal p ojec ion AN o he iden i y ma ix on o he
subspace ASby i s expansion wi h espec o an o hono mal basis o AS
[23]. This is he idea o he ollowing lemma.
4
Lemma 2.1. Le A∈Rn×nbe nonsingula . Le Sbe a linea subspace o
Rn×no dimension d, and {M1, ..., Md}a basis o Ssuch ha {AM1, ..., AMd}
is an o hogonal basis o AS. Then, he solu ion o p oblem (1.4) is
N=
d
X
i=1
(AMi)
kAMik2
F
Mi,(2.1)
and he minimum F obenius no m is
kAN −Ik2
F=n−
d
X
i=1
[ (AMi)]2
kAMik2
F
.(2.2)
Rema k 2.1. I we ha e a basis {Mi}d
i=1 o subspace Ssuch ha he co -
esponding basis {AMi}d
i=1 o subspace ASis no o hogonal, hen we only
need o use he G am-Schmid o hogonaliza ion p ocedu e o ob ain an o -
hogonal basis o AS, in o de o apply Lemma 2.1. This p ocedu e has been
o malized in [23], ob aining se e al explici exp essions o bo h he op imal
p econdi ione Nde ined by (1.4) and kAN −IkF, ha ha e been applied
o he spa se p econdi ioning o la ge linea sys ems a ising om eal-wo ld
cases.
Fo di e en spec al p ope ies o ma ix AN, and o he heo e ical
e ec i eness analysis o he op imal app oxima e in e se p econdi ione s N
de ined by Eq. (1.4), we e e he eade o [24, 25].
3. The p oposed app oxima e in e se p econdi ione
In his sec ion, he p oposed p econdi ione No sys em (1.1) is in o-
duced. Fi s , we need o gi e a de ini ion and o se some no a ions.
Compa ing wo di e en app oxima e in e ses o he same ma ix A, as
s a ed by he ollowing de ini ion, is an essen ial poin o p econdi ioning
pu poses.
De ini ion 3.1. Le A, N, N0∈Rn×nand suppose ha Ais nonsingula .
Then, we say ha Nis be e app oxima e in e se o A han N0, o ha N
imp o es N0as app oxima e in e se o Ai and only i
kAN −IkF<kAN0−IkF.
5

Th oughou his pape , he subspace o all n×ndiagonal ma ices is
deno ed by Dn. F om now on, Mi,j deno es he n×nma ix whose only
nonze o e m is mij = 1, eideno es he i h column o he iden i y ma ix
(i.e., Aeiis he i h column o A), and he symbols k·k2and h·,·i2s and o
he usual Euclidean ec o no m and inne p oduc , espec i ely.
Rema k 3.1. No e ha since Mi,j =eieT
j, hen he only non-null column
o ma ix AMi,j is i s j h one, which coincides wi h he i h column Aeio
ma ix A. Consequen ly, we ha e
(AMi,j) = AeieT
j=aji,kAMi,jk2
F=
AeieT
j
2
F=kAeik2
2.(3.1)
Mo eo e ,
hAMi,j, AMi0,jiF=AeieT
j, Aei0eT
jF=hAei, Aei0i2,(3.2)
hAMi,j, AMi0,j0iF=AeieT
j, Aei0eT
j0F= 0 o all j6=j0,(3.3)
so ha any sys em o ma ices {AMi,j}n
j=1 is o hogonal wi h espec o he
F obenius inne p oduc .
When all diagonal en ies o ma ix Aa e no null, he p econdi ione
diag a−1
11 , a−1
22 , . . . , a−1
nn
is o en used as an app oxima e in e se p econdi ione o sys em (1.1); see,
e.g., [2]. Howe e , in gene al, his is no he op imal choice (in he sense
o Eq. (1.4)) among he diagonal app oxima e in e ses. Indeed, as i is
well-known, he bes diagonal p econdi ione Do sys em (1.1), ha is, he
solu ion o p oblem (1.4) o he subspace Dnis gi en by (see, e.g., [27])
D=
n
X
j=1
ajj
kAejk2
2
Mjj =diag a11
kAe1k2
2
,··· ,ann
kAenk2
2!,(3.4)
while he co esponding minimum F obenius no m is gi en by

AD −I
2
F=n−
n
X
j=1
a2
jj
kAejk2
2
.(3.5)
Ob iously, he op imal diagonal app oxima e in e se (3.4) o ma ix A,
has exac ly one nonze o elemen pe column. As men ioned in Sec ion 1,
6
his sugges s he idea o conside ing he bes app oxima e in e se o ma ix
Aamong all he n×nma ices ha ha e exac ly one nonze o elemen pe
column, he so-called op imal ow posi ion o en y pe column. Suppose
ha he nnonze o op imal en ies a e placed a posi ions
(i1,1) ,(i2,2) ,...,(in, n),
i.e., o each column j= 1,2, . . . , n, he op imal en y o p econdi ioning
he linea sys em (1.1), by using Eq. (1.4), is placed a he ij h ow.
Then, ou new p econdi ione Nis de ined as ollows.
(i) I ij=j, he bes en y in he j h column is he diagonal one. We selec
his en y, and no o he en ies a e added o (j, j) in column j.
(ii) I ij6=j, he bes en y in he j h column is no he diagonal one. We
selec he diagonal en y (j, j) and, besides, he op imal en y (ij, j) is added
o column j.
(iii) Finally, ou p econdi ione Nis de ined as he solu ion o p oblem (1.4)
o he subspace So Rn×nwhose only nonze o en ies a e he ones de ined
by s eps (i) and (ii), i.e.,
S=Sn:= span {Mj,j}n
j=1 ∪Mij,j |ij6=jn
j=1.
In his way, he numbe o nonze o en ies o each column j= 1,2, . . . , n
o ma ix Nis ei he 1 (i ij=j) o 2 (i ij6=j). Hence, he o al numbe
o nonze o en ies o he n×np econdi ioning ma ix Nis a leas nand a
mos 2n.
Fo ins ance, le n= 4 and suppose ha o a ce ain coe icien ma ix
A∈R4×4, he op imal posi ions pe column a e
(i1,1) = (1,1) ,(i2,2) = (4,2) ,(i3,3) = (3,3) ,(i4,4) = (1,4) .
Then, he spa si y pa e ns o he p econdi ioning ma ices Dand Nwill be
D=



n11 000
0n22 0 0
0 0 n33 0
000n44



, N =



n11 0 0 n14
0n22 0 0
0 0 n33 0
0n42 0n44



,
whe e n42 and n14 a e he new (op imal) en ies in N, no appea ing in D.
Hence
S4=span {M1,1, M2,2, M3,3, M4,4, M4,2, M1,4}.
7
Rema k 3.2. No e ha he p econdi ioning ma ix Ngene alizes he op-
imal diagonal app oxima e in e se D. Indeed, in he special case ha he
op imal en y o each column j= 1,2, . . . , n is he diagonal one, we ha e
ij=j o all j= 1,2, . . . , n ⇒N=D.
Mo eo e , he p econdi ione Nimp o es, in gene al, he op imal diagonal
p econdi ione D. Indeed, since Dand Na e he solu ions o p oblem (1.4)
o he subspaces
Dn=span {Mj,j}n
j=1 and Sn=span {Mj,j}n
j=1 ∪Mij,j |ij6=jn
j=1,
espec i ely, hen we ha e
Sn⊇ Dn⇒ kAN −IkF≤
AD −I
F.
The ollowing is he main esul o his pape . I p o ides us wi h explici
exp essions o bo h ma ix Nand he minimum F obenius no m kAN −IkF.
Theo em 3.1. Le A∈Rn×nbe nonsingula . Le Nbe he solu ion o
p oblem (1.4) o he subspace
Sn=span {Mj,j}n
j=1 ∪Mij,j |ij6=jn
j=1.(3.6)
Then, o each j= 1,2, . . . , n, i s co esponding index ijis de ined by he
condi ion ajij

Aeij
2
= max |aj1|
kAe1k2
,|aj2|
kAe2k2
,··· ,|ajn|
kAenk2.(3.7)
Mo eo e ,
N=
n
X
j= 1
ij=j
ajj
kAejk2
2
Mj,j +
n
X
j= 1
ij6=j
ajj 
Aeij
2
2−ajijAej, Aeij2
kAejk2
2
Aeij
2
2−Aej, Aeij2
2
Mj,j
+
n
X
j= 1
ij6=j
ajijkAejk2
2−ajj Aej, Aeij2
kAejk2
2
Aeij
2
2−Aej, Aeij2
2
Mij,j (3.8)
8
and he co esponding minimum F obenius no m is gi en by
kAN −Ik2
F=n−
n
X
j=1
a2
jj
kAejk2
2
−
n
X
j= 1
ij6=j
ajijkAejk2
2−ajj Aej, Aeij22
kAejk2
2kAejk2
2
Aeij
2
2−Aej, Aeij2
2.(3.9)
P oo . Fi s , we de e mine he (op imal) posi ions {(ij, j)}n
j=1 o he nonze o
en ies in he bes app oxima e in e se o ma ix Aamong all n×nma ices
ha ha e exac ly one nonze o elemen pe column.
Le j∈ {1,2, . . . , n}be a bi a y, bu ixed. The op imal app oxima e
in e se Ni,j, among all he n×nma ices whose only nonze o e m is placed
a he i h ow, j h column, can be ob ained as he solu ion o p oblem (1.4)
o he one-dimensional subspace S=span {Mi,j}. Tha is, using Eqs. (2.1)
and (3.1), we ob ain
Ni,j = (AMi,j)
kAMi,jk2
F
Mi,j =aji
kAeik2
2
Mi,j,
o which, using Eqs. (2.2) and (3.1), we ha e
kANi,j −Ik2
F=n−[ (AMi,j)]2
kAMi,jk2
F
=n−a2
ji
kAeik2
2
.
Consequen ly, he index i∈ {1,2, . . . , n} ha minimizes kANi,j −Ik2
F o
each ixed column j, is he one ha maximizes he quo ien a2
ji
kAeik2
2
, ha is,
he index ij, de ined by Eq. (3.7).
Now, conside he se
T={j∈ {1,2, . . . , n} | ij6=j}.
The e a e wo possible cases.
Case 1. I ij=j o all j= 1,2, . . . , n hen T=∅. In his case,
Sn=span {Mj,j}n
j=1 ∪Mij,j |ij6=jn
j=1=span {Mj,j}n
j=1 =Dn.
9
P oo . Using he ob ious ac ha
kA−Ik2
F=n−2 (A)−kAk2
F
and Eqs. (3.9) and (3.15), we ob ain
kA−Ik2
F−kAN −Ik2
F=kAk2
F−2 (A) +
n
X
j=1
a2
jj
kAejk2
2
+
n
X
j= 1
ij6=j
ajijkAejk2
2−ajj Aej, Aeij22
kAejk2
2kAejk2
2
Aeij
2
2−Aej, Aeij2
2
≥
n
X
j=1 kAejk2
2−
n
X
j=1
2ajj +
n
X
j=1
a2
jj
kAejk2
2
+
n
X
j= 1
ij6=j
ajij

Aeij
2−|ajj|
kAejk2!2
1
sin2θj
=
n
X
j=1 kAejk2
2−ajj2
kAejk2
2
+
n
X
j= 1
ij6=j
ajij

Aeij
2−|ajj|
kAejk2!2
1
sin2θj
.
Finally, i kAejk2
26=ajj o a leas one index j= 1,2, . . . , n hen he le
sum in Eq. (3.17) con ains a leas one posi i e summand, and hus we
conclude ha kA−IkF>kAN −IkF. Mo eo e , i ma ix Nis no di-
agonal hen ij6=j o a leas one column j∈ {1,2, . . . , n}(case 2 in he
p oo o Theo em 3.1). Hence, he igh sum in Eq. (3.17) con ains a
leas one summand, which is necessa ily posi i e due o Eq. (3.7), and hus
kA−IkF>kAN −IkF.
Rema k 3.6. Co olla y 3.1 has es ablished he compa ison be ween he op-
imal diagonal p econdi ione Dand he p oposed p econdi ione N, in he
16

ollowing e ms. Fi s , no e ha om Eqs. (3.7) and (3.16), we conclude
ha Nimp o es Din he sense o De ini ion 3.1, i.e.,
I N6=D⇒ ∃ j∈ {1,2, . . . , n}s. . ij6=j⇒
AD −I
F>kAN −IkF.
Second, Eq. (3.16) p o ides us wi h he ollowing analysis o he imp o emen
achie ed when using p econdi ione Nins ead o p econdi ione D. Fo he
second i em, we use he ob ious ac ha he unc ion (θ) = 1
sin2θis s ic ly
dec easing in he in e al 0,π
2, and s ic ly inc easing in he in e al π
2, π.
(i) Fo each j= 1,2, . . . , n such ha ij6=j, he mo e he maximum quo ien
|ajij|
kAeijk2
(gi en by Eq. (3.7)) exceeds he quo ien |ajj |
kAejk2
, he la ge he di e -
ence 
AD −I
2
F−kAN −Ik2
Fwill be, and hus he mo e he p econdi ione
Nimp o es he diagonal p econdi ione D(in he sense o De ini ion 3.1).
(ii) Fo each j= 1,2, . . . , n such ha ij6=j, he close he angle θjbe ween
he j h and he ij h columns o he coe icien ma ix Ais ei he o 0 o o
π(i.e., he la ge he di e ence be ween θjand π
2is), he la ge (θj), and
hen he la ge he di e ence 
AD −I
2
F−kAN −Ik2
Fwill be, and hus he
mo e he p econdi ione Nimp o es he diagonal p econdi ione D(in he
sense o De ini ion 3.1).
Rema k 3.7. No e ha he igh -mos sum in Eq. (3.17) coincides wi h he
sum in Eq. (3.16). Thus, he abo e wo commen s (i) and (ii) in Rema k 3.6,
conce ning he compa ison be ween 
AD −I
Fand kAN −IkF(analyzed
in Co olla y 3.1), emain ue o he compa ison be ween kA−IkFand
kAN −IkF(analyzed in Co olla y 3.2).
Rema k 3.8. Call N1=N he app oxima e in e se o ma ix A, con-
s uc ed in Theo em 3.1. Acco ding o he well-known mul is ep p econ-
di ioning s a egy (see, e.g., [15, 26]), we can ob ain a sequence N1,N1N2,
N1N2N3, . . . o app oxima e in e ses o Awhe e, o e e y k≥2, ma ix Nk
is he bes spa se app oxima e in e se o ma ix AN1N2···Nk−1, among all
ma ices de ined by he spa si y pa e n (3.6).
No e ha since subspace Dno all n×ndiagonal ma ices is closed o
he ma ix p oduc , hen we ha e
min
M∈Dnk(AN1)M−IkF=k(AN1)N2−IkF=kA(N1N2)−IkF
min
M∈DnkA(N1M)−IkF= min
M∈DnkAM −IkF=kAN1−IkF,
17
and hen, due o he uniqueness o solu ion o p oblem (1.4), we conclude
ha N1N2=N1. This means ha he mul is ep s a egy does no make
sense o he op imal diagonal p econdi ione . Howe e , his does no happen
wi h he op imal p econdi ione s Nbelonging o he subspaces Snde ined
by he p esc ibed spa si y pa e ns (3.6) and hus, in ou case he mul is ep
p econdi ioning s a egy makes sense. In pa icula , Eq. (3.18) implies ha
each s ep ko ou mul is ep p econdi ioning s a egy s ic ly educes he
F obenius no m, whene e he p econdi ione Nk−1, ob ained in he p e ious
s ep, is no diagonal.
4. Nume ical expe imen s
We p esen some nume ical expe imen s o illus a e he beha io o he
p oposed p econdi ione N. We compa e he p econdi ioned linea sys em
using ou p econdi ione Nwi h bo h he unp econdi ioned linea sys em
and he p econdi ioned sys em using he op imal diagonal p econdi ione D.
A he end o his sec ion, he p econdi ione Nis also compa ed wi h he ap-
p oxima e in e se p econdi ione AINV. We ha e s udied a numbe o linea
sys ems Ax =b, whe e he es coe icien ma ices a e aken om he Uni-
e si y o Flo ida Spa se Ma ix Collec ion [28]. We ca ied ou ou nume i-
cal p oblems wi h he K ylo sol e s GMRES [29] and BiCGS ab [30]. Bo h
sol e s led o simila esul s o mos es ma ices, bu a small ad an age was
obse ed when using he la e o sol ing he sys ems p econdi ioned wi h
ma ix N. Fo his eason, we only p esen he e he esul s ob ained wi h
he ( igh -p econdi ioned) BiCGS ab. In any case, ou pu pose in his pape
is o analyze he e ec i eness o he p oposed p econdi ione (especially in
compa ison wi h he op imal diagonal app oxima e in e se), a he han o
compa e di e en K ylo subspace me hods. The ini ial guess was always
x0= 0, and he igh -hand side ec o was b= [1,...,1]T. The s opping
c i e ion was ei he kb−Axkk2
kbk2
<10−8,
o when his condi ion abou he ela i e esidual was no sa is ied, wi hin
2ni e a ions (nbeing he o de o he coe icien ma ix A). We un all
nume ical expe imen s in double p ecision a i hme ic, on In el(R)Xeon(R)
E5620 wi h 2.40 GHz clock equency and 24GB o main memo y using GNU
Oc a e 3.2.4.
18
In Table 1, nand nnz (A) s and o he o de and he numbe o nonze o
en ies o ma ix A, espec i ely. This able also p o ides he F obenius
no ms o ma ices A−I,AD −Iand AN −I.
In Table 2, nnz (N) deno es he numbe o nonze o en ies o ou p econ-
di ione N, which is compa ed, in i s second column, wi h he numbe no
en ies o he op imal diagonal p econdi ione D(ob iously, n≤nnz (N)≤
2n). In he hi d and ou h columns, D- ime and N- ime deno e he CPU
ime (in seconds) o cons uc ing he p econdi ione s Dand N, espec i ely.
In he h ee igh -mos columns, Unp ec-i e , D-i e , and N-i e s and o
he numbe o i e a ions o he BiCGS ab me hod o he unp econdi ioned
sys em, and he p econdi ioned sys ems wi h Dand N, espec i ely. When
con e gence is no a ained, wi hin he maximum numbe 2no allowed i -
e a ions, we indica e i by w i ing “†”, in any o he co esponding columns
Unp ec-i e , D-i e and N-i e .
Nume ical es s epo ed con i m he heo e ical esul s and illus a e he
e ec i eness o he p oposed p econdi ione in compa ison wi h he op imal
diagonal one.
Tes p oblems ha e been g ouped oge he in o i e classes, acco ding o
he beha io o he p econdi ione Nin compa ison wi h D. Looking a
he wo igh -mos columns (D-i e and N-i e ) in Table 2, one can easily
iden i y each o hese i e g oups o es ma ices. Fo each o hese classes,
p oblems a e a anged in inc easing o de o he size no he es coe icien
ma ices.
The i s i e es p oblems co espond o ma ices o which he op imal
diagonal p econdi ione and ou p econdi ione coincide, i.e., N=D. O
cou se, his is in acco dance wi h he heo y, since Nhas been de ined as a
gene aliza ion o D, and hey do coincide when ij=j o all j= 1,2, . . . , n.
Ob iously, in such cases, Table 2 shows ha nnz (N) = n(each column o
Nconsis s only o i s diagonal en y), and he numbe o i e a ions needed
o con e gence coincide o bo h p econdi ione s.
The es o es ma ices co esponds o he case N6=D, so ha he
numbe nnz (N) o nonze o en ies o Nwill be g ea e han n. When
nnz (N) = 2n, his means ha ij6=j o all j= 1,2, . . . , n, and each
column o Nconsis s o wo nonze o en ies.
19
Table 1
The es ma ices and he F obenius no ms o A−I,AD −Iand AN −I.
Ma ix n nnz (A)kA−IkF
AD −I
FkAN −IkF
o si 2 886 5970 1.55 ×10618 18
she man1 1000 3750 1.00 ×10315.6 15.6
she man4 1104 3786 1.21 ×10310.4 10.4
bcss k09 1083 18437 8.57 ×10821.2 21.2
she man3 5005 20033 1.36 ×10727.2 27.2
ho 131 434 4182 4.34 ×10214.7 14.7
db450l 450 2580 5.01 ×10216.2 13.7
po es 3 532 3474 6.63 ×10515.1 14.9
s eam2 600 5660 5.27 ×1010 16.8 12.3
young3c 841 3988 6.40 ×10314.8 14.7
bcss k10 1086 22070 2.97 ×10822.6 22.6
olm500 500 1996 2.24 ×10518.3 15.6
olm1000 1000 3996 1.26 ×10625.8 22.1
ols1090 1090 3546 1.23 ×10716.8 14.6
pga ans 01 1220 7382 1.22 ×10324.6 22.4
adde dcop 14 1813 11246 1.81 ×10324.3 23.9
adde dcop 15 1813 11246 1.81 ×10324.4 24
adde dcop 16 1813 11246 1.81 ×10324.1 23.7
adde dcop 17 1813 11246 1.81 ×10324 23.6
adde dcop 20 1813 11246 1.81 ×10324 23.5
adde ans 02 1814 14579 1.81 ×10314.6 14.1
ols2000 2000 5184 5.40 ×10721.6 18.7
psmig 1 3140 543160 3.54 ×10615.4 15.4
ols4000 4000 8784 2.98 ×10829.5 25.5
meg4 5860 25258 9.87 ×10517.4 15.8
s eam1 240 2248 8.41 ×1078.95 8.92
she man5 3312 20793 1.44 ×10432.4 32.3
she man2 1080 23094 7.00 ×10930.7 28.9
adde dcop 10 1813 11232 1.81 ×10325.2 24.7
20
Table 2
Con e gence esul s o Dand N.
Ma ix nnz (N)/n D- ime N- ime Unp ec-i e D-i e N-i e
o si 2 886/886 0.072 0.360 1232 448 448
she man1 1000/1000 0.084 0.368 407 192 192
she man4 1104/1104 0.096 0.408 92 64 64
bcss k09 1083/1083 0.124 0.832 188 154 154
she man3 5005/5005 1.56 6 †453 453
ho 131 435/434 0.028 0.140 †369 255
db450l 900/450 0.024 0.380 †254 51
po es 3 560/532 0.032 0.188 †717 637
s eam2 750/600 0.044 0.324 448 10 7
young3c 849/841 0.072 0.304 1080 974 804
bcss k10 1088/1086 0.136 0.936 †736 657
olm500 1000/500 0.032 0.428 † † 307
olm1000 2000/1000 0.084 0.996 † † 657
ols1090 1568/1090 0.088 0.688 † † 1560
pga ans 01 1352/1220 0.128 0.684 † † 205
adde dcop 14 1834/1813 0.248 1.224 † † 437
adde dcop 15 1836/1813 0.248 1.220 † † 310
adde dcop 16 1837/1813 0.248 1.224 † † 418
adde dcop 17 1843/1813 0.248 1.228 † † 329
adde dcop 20 1857/1813 0.248 1.248 † † 518
adde ans 02 1832/1814 0.260 1.384 229 †9
ols2000 2842/2000 0.256 1.560 † † 1534
psmig 1 3143/3140 4.348 46.951 1812 †58
ols4000 5642/4000 0.896 4.492 † † 1328
meg4 5968/5860 2.104 8.584 † † 5
s eam1 320/240 0.012 0.108 †236 388
she man5 3327/3312 0.756 3.53 2251 849 892
she man2 1628/1080 0.144 1.38 † † †
adde dcop 10 1872/1813 0.248 1.256 † † †
In some o hese cases (e.g., o he es ma ices displayed in ows 6-11),
he numbe o i e a ions needed o each con e gence is educed when using
ou p econdi ione Nins ead o D.
Mo eo e , in many cases, like o ins ance o he es ma ices displayed
in ows 12-25 in Table 2, con e gence is no a ained wi h he diagonal p e-
21

condi ione D, bu howe e i is eached when we use ou p econdi ione N.
We hink ha his is he main ad an age o ou p econdi ione poin ed ou
by he nume ical es s.
In pa icula , we highligh he case o he es ma ix psmig 1. In his
case, al hough he p econdi ione Nhas only 3 nonze o en ies mo e han he
diagonal p econdi ione D(nnz (N)/n = 3143/3140), he sys em ansi s
om non-con e gence o con e gence i we use N(wi h a small numbe
o i e a ions) ins ead o Das p econdi ioning ma ix. Mo eo e , o his
es p oblem, bo h p econdi ione s only di e in he nume ical alues o 6
en ies: he nnz (N)−n= 3 diagonal en ies (j, j) o which ij6=j, and
he co esponding 3 nondiagonal en ies (ij, j) ha do no appea in he
diagonal ma ix D. The nume ical alues o he emaining n−3 = 3137
nonze o diagonal en ies o Dand Ncoincide (see Eqs. (3.4) and (3.8)). So,
Dand Na e e y simila bu , as men ioned, we ob ain con e gence wi h he
la e , bu no wi h he o me . This happens no only o he es p oblem
psmig 1, bu also o o he es ma ices epo ed.
Nex , we p esen wo p oblems, namely he hi d and ou h ones om he
bo om, o which he numbe o i e a ions equi ed o eaching con e gence
is g ea e when we use he p econdi ione Nins ead o D. Finally, o he las
wo es ma ices epo ed, con e gence is eached nei he wi h Nno wi h
D. This can be explained by he small numbe o nonze o en ies in bo h
p econdi ione s, which makes hem ine icien o some e y ill-condi ioned
sys ems.
Fo all es p oblems epo ed, he las h ee columns in Table 1 con i m
ou heo e ical esul s, in he sense ha
kA−IkF≥
AD −I
F≥ kAN −IkF.
On one hand, he i s inequali y is due o he ac ha he op imal
diagonal p econdi ione D(by de ini ion) minimizes kAM −IkFo e he
subspace o all n×ndiagonal ma ices (and he iden i y is a diagonal ma ix).
On he o he hand, he second inequali y is an ob ious consequence o he
se inclusion Sn⊇ Dn(as commen ed in Rema k 3.2).
The la ge di e ence (obse ed o all es ma ices epo ed) be ween
kA−IkFand any o he alues 
AD −I
Fand kAN −IkFis mainly due o
he ollowing ac . While, ob iously, kA−IkFcan be a bi a ily la ge, bo h
no ms 
AD −I
Fand kAN −IkFa e ne e g ea e han √n. The eason
is ha , om Eq. (2.2) we immedia ely de i e ha he op imal app oxima e
22
in e se M(in he F obenius sense) o e any ma ix subspace S ⊂ Rn×n
(and, in pa icula , M=Dand M=N) always sa is ies kAM −IkF≤√n.
Also, we can obse e ha he es ma ices o which he di e ence be ween

AD −I
Fand kAN −IkFis la ge usually co espond o hose cases o
which he a io be ween he numbe s o nonze o en ies in ma ices Nand D
(deno ed by nnz (N)/n in Table 2) is la ge . In addi ion o his a io, o he
pa ame e s ha also de e mine he di e ence be ween ( he squa es o ) he
F obenius no ms o AD −Iand AN −Iha e been analyzed in Rema k 3.6.
Summing up, in almos all he cases, he i e a ions equi ed by he
BiCGS ab me hod when using p econdi ione Na e ewe han hose needed
by his sol e when using he diagonal p econdi ione D. The di e ences be-
ween he CPU imes o cons uc ing he p econdi ione s Dand N, as well
as he di e ences be ween he execu ion imes o he BiCGS ab me hod o
bo h p econdi ione s, a e no signi ican , and in mos cases he o al CPU
imes o sol ing he sys em wi h Dand Na e o he same o de o mag-
ni ude. In any case, he small inc emen in compu a ional cos when using
he p econdi ione Nins ead o D, is compensa ed by he ac ha , in many
cases, con e gence is eached wi h he p econdi ione Nbu no wi h he
op imal diagonal p econdi ione D.
Fo bo h p econdi ione s Dand N, hei espec i e spa si y pa e ns con-
sis o small numbe s o nonze o en ies (nen ies o D, and a numbe o
en ies be ween nand 2n o N). On one hand, his implies low compu a-
ional cos s o cons uc ing hem. On he o he hand, o bo h o hem,
he numbe o equi ed i e a ions is la ge in compa ison wi h o he mo e
dense and expensi e op imal app oxima e in e se p econdi ione s based on
he same idea (F obenius no m minimiza ion). In any case, as he nume ical
expe imen s ha e shown, he p oposed p econdi ione imp o es he classical
diagonal one, wi h a small inc emen in he compu a ion cos equi ed o
cons uc ing he o me ins ead o he la e .
To inish his sec ion, we compa e he p oposed p econdi ione Nwi h a
mo e expensi e app oxima e in e se p econdi ione , namely he well-known
AINV p econdi ione [6]. We ha e implemen ed he AINV p econdi ione ,
wi h a d op ole ance Tol = 0.25, o he same se o es ma ices used o
compa ing ou p econdi ione Nwi h he op imal diagonal one D. Fo mos
o hese es p oblems, AINV was ound o be mo e e icien (in e ms o
he o e all solu ion ime and using he K ylo sol e BiCGS ab) han N.
Howe e , o some es ma ices, namely she man4,s eam2,adde ans 02,
23
psmig 1 and meg4, he p oposed p econdi ione was ound o be mo e e i-
cien han AINV. In conclusion, ou p oposed p econdi ione was mo e e ec-
i e han he op imal diagonal D o mos o he nume ical p oblems consid-
e ed in his pape , and i was mo e e ec i e han he AINV p econdi ione
in a ew cases.
5. Summa y and conclusions
In his pape , a new app oxima e in e se p econdi ione N o la ge spa se
linea sys ems has been cons uc ed and heo e ically analyzed. Nhas been
de ined as he op imal p econdi ione (in he F obenius sense) among all he
n×nma ices whose only nonze o en ies, o each column j= 1,2, . . . , n, a e
he diagonal one (j, j) and, in addi ion, he op imal en y (ij, j) in column
j, whene e i does no coincide wi h he diagonal one. In his way, ou
p econdi ioning ma ix Ngene alizes he op imal diagonal p econdi ione D.
Explici exp essions o bo h ma ix Nand he minimum F obenius no m
kAN −IkFha e been p esen ed. We ha e p o ed ha , whene e N6=D,
he p econdi ione N(which has a leas nand a mos 2nnonze o en ies)
imp o es D, in he sense o he F obenius no m. We ha e also analyzed he
di e ence be ween he F obenius no ms o A−Iand AN −I.
Nume ical expe imen s ha e con i med he heo e ical esul s, p esen ing
a numbe o es ma ices o which he p oposed p econdi ione imp o es
he con e gence o he op imal diagonal one, when hey do no coincide.
In pa icula , Table 1 shows ha he F obenius no m kAN −IkFis always
smalle (as we ha e heo e ically shown) and, in ac , much smalle in mos
cases han he F obenius no m kA−IkF. Table 2 illus a es he educ ion,
in mos cases, o he numbe o i e a ions when we use he p econdi ioning
ma ix Nins ead o D.
The main ad an age o ou p econdi ione poin ed ou by he nume ical
es s is he ollowing. Fo many es ma ices, he small addi ional CPU
ime equi ed o cons uc ing Nins ead o Dis compensa ed by he ac
ha sys em ansi s om non-con e gence o con e gence when using N
ins ead o Das p econdi ioning ma ix. Mo eo e , his also occu s o some
es p oblems o which he numbe o nonze o en ies o he p econdi ione
Nexceeds only by a e y small quan i y he numbe o nonze o en ies o he
diagonal p econdi ione D, and he nume ical alues o mos o he en ies
placed a he same diagonal posi ions coincide o bo h p econdi ione s (D
and Na e e y simila ).
24
Fo u u e esea ches, i would be in e es ing o analyze in mo e de ail
he p ac ical alue o he p econdi ione p oposed in his pape . Fo his
pu pose, ou p econdi ione Ncould be compa ed, using new es ma ices,
wi h he AINV app oxima e in e se p econdi ione and wi h o he p econdi-
ione s no conside ed in his pape . In addi ion, i is wo h ying o s udy
some common cha ac e is ics/ ea u es o hose es ma ices o which he
gene alized p econdi ione Nhas a be e beha io o con e gence pu poses.
Finally, ega ding an addi ional line o u u e wo k, ou me hod can be
imp o ed by conside ing he op imal p econdi ione N(in he sense o he
F obenius no m) among all he n×nma ices ha ing exac ly a (small) ixed
numbe mj≥2 o nonze o en ies o each column j= 1,2, . . . , n.
The de e mina ion o he spa si y pa e n o such p econdi ione Nis no
a simple p oblem because o he ollowing ac . Assume ha he j h column
Nejo he p econdi ione Nconsis s o only one nonze o en y, i.e., mj= 1.
Then, as shown in Sec ion 3, he op imal posi ion i1
j, jin he j h column
Nejo N o minimizing kANej−ejk2can be easily de e mined simply by
using Eq. (3.7). Simila ly, we can easily de e mine he second, hi d,...,mj h
bes posi ions i2
j, j,i3
j, j,...,imj
j, jin he j h column o N o minimizing
kANej−ejk2. Un o una ely, he se o hese bes mjposi ions (ob ained
sepa a ely, i.e., when Nejconsis s o only one nonze o en y) o app oxi-
ma ing he j h column ejo I, does no necessa ily coincide wi h he op imal
se o ca dinali y mj o app oxima ing ej(when he spa si y pa e n o N
is de ined by he condi ion ha Nejconsis s o mj≥2 nonze o en ies).
Consequen ly, he de e mina ion o his op imal mj-se (in o de o ind he
op imal spa si y pa e n o an op imal p econdi ione de ined by Eq. (1.4))
is a e y di icul p oblem (when mj≥2). Al e na i ely, one can conside he
possibili y o using an algo i hm based on he LU ac o iza ion wi h pa ial
pi o ing o de e mine he op imal spa si y pa e n o each column.
Acknowledgmen s
The au ho s hank he anonymous e e ees o hei de ailed e isions
and aluable commen s and sugges ions, which ha e subs an ially imp o ed
he ea lie e sion o his pape . This wo k was pa ially suppo ed by he
“Minis e io de Econom´ıa y Compe i i idad” o he Spanish Go e nmen , and
FEDER, h ough G an con ac : CGL2011-29396-C03-01.
25