Editor: Ched E. Stedman, pp. 73-109 c 2006 Nova Science Publishers, Inc.
Chapter 3
O
N THE
B
EST
L
EAST
S
QUARES
F
IT TO A
M
ATRIX
AND
I
TS
A
PPLICATIONS
Carmine Di Fiore
, Stefano Fanelliy
and Paolo Zelliniz
Universit`a di Roma “Tor Vergata”,
Via della Ricerca Scientifica 1, 00133 Roma, Italy
Abstract
The best least squares fitL
Ato a matrix
Ain a spaceLcan be useful to improve the
rate of convergence of the conjugate gradient method in solving systemsAx =bas
well as to define low complexity quasi-Newton algorithms in unconstrained minimiza-tion. This is shown in the present paper with new important applications and ideas. Moreover, some theoretical results on the representation and on the computation of
L
Aare investigated.
1
Introduction
In this paper the concept of matrix approximation is linked to a general strategy or to an idea which has been proposed in a number of previous papers and tested for several problems of numerical linear algebra and numerical optimization. The idea is simply the following one: reduce a computational problem involving linear operators non sufficiently structured to a framework where only matrices with a special structure are present, and where the essential computation consists, finally, in a small number of fast transforms. This reduction has been used in different contexts, and is turned out to be an effective tool for analyzing the complexity and improving the efficiency of algorithms. For instance, the very special properties of matrix algebras of Jacobi type are used in [7] to calculate the eigenvalues of symmetric Toeplitz matrices and in [8], [47] to find the multiplicative complexity of a set of Toeplitz bilinear forms. Circulant, Jacobi, and Hartley-type matrices are usually exploited in preconditioning techniques [42], [18], [9], [16], [21], [30]. In displacement theory [39],
E-mail address: [email protected]
y
E-mail address: [email protected]
z
-0.5 1 p L(-0.5)=Hartley algebra
Figure 1: The graphic ofkL(p) T
Tk 2
F
: Hartley is not optimal
[38], one can solve a linear system Ax = b by representing A 1
as the sum of a small number of products of matrices belonging to Hessenberg [29], [12], or more general [23], [4], algebras. Finally, in quasi-Newton algorithms for unconstrained minimization, a crucial reduction of (time and space) complexity is obtained by iterations involving special Hessian approximations diagonalized by fast transforms [25], [11].
The reduction of non sufficiently structured problems to structured ones is performed via matrix approximation in Frobenius norm, i.e. by replacing a matrixAby its best least
squares (l.s.) fitL
A, where the matrix L
Abelongs to a fixed algebra
L. Part of the paper is
devoted to a review and to a further investigation of previous results obtained in [30], [25]. Moreover, several new results, applications and ideas are presented.
The seed of the research which finally resulted in [30] and then in [25], consisted in the graphic of Figure 1. It represents the error in approximating a33symmetric Toeplitz
matrixT = (t i j
) in a class L(p), p 2 R, of matrix algebras studied in [23], or, more
precisely, the rational function in the equality
min X2L(p) kX Tk 2 F kL(p) T Tk 2 F = 10p 2 +4p+4 9(p 2 +p+1) (t 1 t 2 ) 2 ; p2R; (1:1) wherekXk F = p tr(X
X)is the Frobenius norm ofX.
The Hartley algebra H, previously introduced in [9], is a member ofL(p), and
corre-sponds to the valuep = 1=2. In [9] it is shown thatH
T, i.e. the best least squares (l.s.)
fit toT inH, can be an efficient preconditioner in solving Toeplitz systemsTx=bby the
conjugate gradient (CG) metod. Figure 1 shows clearly thatT can be approximated better
by picking up in the classL(p) an algebra different fromH = L( 1
2
) and precisely the
new matrix algebra =L(0). This obviously suggested the study of
T and other matrices L(p)
T as new preconditioners.
The contents of this paper are described here below.
In Section 2, we point out the main properties of the best least squares fitL Ato a
nn
matrixA. Some of the remarks included are new and all of them are useful in computing L
A. Several examples and problems are reported. Two possible applications of L
A are
In Section 3, L
A is exploited as a preconditioner in solving positive definite linear
systemsAx=bby theCGmethod. The spaceLis a diagonal spacesdU =fUd(z)U : z2C n g, i.e. P 1 Ax=P 1 b; P =L A =Ud(z A )U
whereU is a unitary matrix andd(z)=diag (z i
;i=1;:::;n). In particular,Lcan be the
algebraH, the algebraor, more in general, a Hartley-type matrix algebra. Recall that the
set of Hartley-type algebras was proposed in [10] as the Hartley counterpart of the known classification of Jacobi transforms/algebras. Theoretical and numerical results on the use ofL
Aas a preconditioner are reported in the cases
A=T,T=symmetric Toeplitz [30] and A=T
T
T,T=generic (non symmetric) Toeplitz.
In Section 4,L
Ais involved in a novel low complexity quasi-Newton procedure for the
unconstrained minimization of a functionf :R n
!R. The new algorithm is based on the
following approximation of the Hessianr 2
f(x
k+1
)in terms of the updating function (4.1): B k+1 ='(U k d(v )U k ;s k ;y k ); s k =x k+1 x k ; y k =rf(x k+1 ) rf(x k )
where the unitary matrix U
k and the vector
v are defined in terms of s k 1,
y
k 1 and a
suitable vectorwas follows:
1. wis such thatU k 1 d(w )U k 1 =L k 1 B k withL k 1 =sdU k 1, 2. U kis such that U k d(z)U k s k 1 =y
k 1for some vector
zclose tow, and
3. v=worv=z.
Item (1) implies that the eigenvalues of the matrixA k :=U k d(w )U k
are strictly related to the eigenvalues ofB
k and can be easily calculated. By item (2) the structure of L k = fU k d(z)U k : z 2 C n g is such that A 0 k := U k d(z)U k shares with B k the property of mapping s k 1 into y
k 1. Thus, the updated matrix, U k d(v )U k , inherites from B k both
spectral and structural properties. Moreover, since iterations involve onlyvand sinceU k
is the product of two Householder matrices, all computations can be written in terms of single indexed arrays only. Thus, O(n)arithmetic operations per step and O(n)memory
allocations are sufficient to implement the algorithm. So, the most significant properties of the LQN methods [25], [11], [24], and of the more recent L
k
QN methods [27] are
inherited by the new algorithm.
2
The Best Least Squares Fit to a Matrix
Let J 1 ; J 2 ;:::;J m be
m linearly independent nn matrices and consider the mm
hermitian matrixBwith entries
b ij =(J i ;J j )= n X r;s=1 [J i ℄ rs [J j ℄ rs : (2:1)
From the identity
x Bx= n X m X x j [J j ℄ rs 2 ; x2C m ; (2:2)
one deduces thatBis a hermitian positive definite matrix.
Problem 1: Given ammhermitian positive definite matrixB, is it possible to define mlinearly independentnnmatricesJ
1 ; J 2 ; :::; J msuch that (J i ;J j )=[B℄ ij?
The matrixB in (2.1) arises when calculating the best least squares (l.s) fit to a matrix Ain the spaceLspanned by theJ
k, i.e. when solving the following
Problem 2.1 Find the complex numbers
kfor which k m X k=1 k J k Ak F k m X k=1 k J k Ak F ; 8 k 2C; (2:3)
whereAis any fixednnmatrix andkk
F is the Frobenius norm.
In fact, by the Hilbert projection theorem, Problem 2.1 is well posed, i.e. there is a unique vector = [ 1 2 m
℄ satisfying the inequality (2.3) or, equivalently, the
orthogonality conditions (J i ; m X k=1 k J k A)=0; i=1;:::;m: (2:4) Such vector is =B 1 ; i =(J i ;A)= n X r;s=1 [J i ℄ rs [A℄ rs : (2:5) Moreover, since k P n k=1 k J k Ak 2 F = B 2Re ( )+kAk 2
F, one has the
following expressions for the error
k n X k=1 k J k Ak 2 F =kAk 2 F B =kAk 2 F k n X k=1 k J k k 2 F : (2:6)
Finally, observe that ifAis real (hermitian), then also P n k=1 k J kis real (hermitian), provided thatJ k =J k( J k 2SpanfJ 1 ;:::;J n g).
Thus the computations required in order to solve Problem 2.1 are: 1. Calculate the inner products
i =(J
i ;A)
2. CalculateBand solve the systemBz=
The error may be calculated via (2.6). Definition 2.2 CallL Athe matrix P m k=1 k J
ksatisfying (2.3), (2.4). We have obviously
L A = m X [B 1 ℄ k J k : (2:7)
Example 1. An n-dimensional space L often used in numerical linear algebra is the space =SpanfJ 1 ;:::;J n gwhere J k = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 0 0 1 0 0 .. . . .. 1 0 1 . .. .. . .. . . .. . .. . .. 1 . .. ... ... .. . 0 1 . . . . .. . .. ... ... ... ... 1 0 1 . .. ... 1 0 0 1 . .. ... 1 0 1 .. . . .. ... ... ... . .. . .. 1 0 .. . . .. ... ... 1 . . . . .. . .. ... .. . . .. 1 0 1 . . . .. . 0 0 1 0 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 withe T 1 J k = e T k
. For the definition and the first applications of see [3], [47], [48], [7],
[8]. Notice thatJ k = J k 1 J 2 J k 2, J
1 is the identity matrix
I andJ
n is the reversing
matrixJ. Forn=4one calculates
B = 2 6 6 4 4 0 2 0 0 6 0 2 2 0 6 0 0 2 0 4 3 7 7 5 ; B 1 = 1 10 2 6 6 4 3 0 1 0 0 2 0 1 1 0 2 0 0 1 0 3 3 7 7 5 : (2:8)
It follows that the best approximation ofAin =SpanfJ 1 ;J 2 ;J 3 ;J 4 gis P 4 k=1 k J k = 1 10 [(3 1 3 )J 1 +(2 2 4 )J 2 +(2 3 1 )J 3 +(3 4 2 )J 4 ; k =(J k ;A): (2:9) Try forn=5.
Assume that the matrixL A = P m k=1 k J
kis required in its explicit form, i.e. replace
Problem 2.1 with
Problem 2.3 Find the matrixL Ain L=SpanfJ 1 ; J 2 ;:::; J m gfor which kL A Ak F kX Ak F ; 8X 2L; (2:10)
whereAis any fixednnmatrix.
If J 0
k
, k = 1;:::;m, are m linearly independent matrices in L, then one finds an
alternative representation ofL A: L A m X k J k = m X 0 k J 0 k ; 0 =B 0 1 0 ; 0 i =(J 0 i ;A); [B 0 ℄ i;j =(J 0 i ;J 0 j ):
As a consequence, once the space L is fixed, one can try to look for a basis J k of L for which the complexity of the inner products (J
i
;A), i = 1;:::;m, is minimal or,
alternatively, for which the systemBz = is easily solvable. The former requirement is
in general satisfied by choosing J
k as sparse as possible. The latter requirement is fully
satisfied by introducing an orthonormal basis of L; in fact, if B = I, then k
=
k are
the Fourier coefficients ofA. Obviously one should be able to construct such orthonormal
basis by a simple procedure, instead of utilizing the Gram-Schmidt algorithm. If the J
k span an algebra
L of group matrices, then the computation of the best least
squares fit of A inL has minimal complexity. This is shown, in the following example,
whenL=fcirculantsg. Example 2. LetJ kbe the nnmatrix J k = 1 p n 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 0 0 1 0 0 .. . 0 . .. ... ... .. . . .. 1 0 0 . .. 1 1 0 0 0 1 . .. .. . .. . . .. ... ... ... 0 0 1 0 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 withe T 1 J k =e T k . Notice that p nJ k = ( p nJ 2 ) k 1 , p nJ 1 = I and J n =J T 2 . For any n
one calculatesB =I. Thus,
C A = n X k=1 k J k = n X k=1 k J k ; k =(J k ;A): (2:11)
Since the matrices J
k are sparse and orthonormal, the computation of the best least
squares fit of Ain the algebra C = SpanfJ 1
;:::;J
n
gof circulant matrices has minimal
complexity. For an exhaustive treatise on circulant matrices see [19].
Notice, however, that circulants are not always the best approximations ofA. In
partic-ular, ifT is a symmetric Toeplitz matrix, then there exist two algebras, andH(see [30],
[9] and Section 3 of this paper), such that
k T Tk F kH T Tk F kC T Tk F : (2:12)
The algebra does not have a simple sparse orthonormal basis asC. However, if one
needs to use the approximationL
T as a preconditioner of the Toeplitz linear system Tx=
b, a little more effort in computingL
T is widely justified by a better approximation level
ofT. In fact, the rate of convergence of the conjugate gradient method applied toTx=b
preconditioned byL
T will be intuitively greater for
L=than forL=C. A formula for
T is obtained in [30]. The inequality (2.12), found in [30], also states that Hartley is not
n = 3). More details on the role ofL
Ain preconditioning techniques for linear systems Ax=bare reported in Section 3.
Best least squares fit inL2V
WhenLis a space of matrices simultaneously diagonalized by a unitary transformU,
some well known properties ofL
A, such as the fact that L
Ainherites the positive
definite-ness from A, are shown in [43], [36], [41]. Now the same properties hold in the more
general case whereLhas a suitableV-structure [30] (see for example Theorem 2.6). This
structure let us also obtain alternative representations of B (defined in (2.1)) especially
useful in computingL A.
We say precisely thatLis aVspace (orLbelongs to the classV) if there exist a vector vand a basisfJ 1 ; J 2 ;:::; J n gofLsuch that v T J k =e T k : (2:13)
A result proving thatV represents a significant class of matrix spaces is the fact that a
matrixX is nonderogatory iff the set of all polynomials inX is a space of classV[30].
Observe that two matrices A 1, A 2 of L 2 V for which v T A 1 = v T A 2, are equal.
This is a sort of generalization of the assertion that two circulant matrices with the same first row are equal. The matrixA =
P n k=1 z k J k is denoted by L v
(z), and the row vector v T A=z T =[z 1 z 2 z n
℄is called thev-row ofA. Forv=e
1simply set
L(z)=L
e1 (z);
soC(z)denotes the circulant matrix with first rowz T
. Problem 2: Given another basisJ
0
k
ofL, is it possible to introduce a vectorv 0 such that v 0T J 0 k =e T k ?
Lemma 2.4 Assume thatL2Vis a matrix algebra, i.e.J i
J
j
2L,8i;j, andI 2L, where I is the identity matrix. If A 2 Lis invertible, then A
1 = L v (z),z T A = v T , i.e. Lis
closed under inversion.
Proof. Letzbe such thatz T A = v T . Sincev T L v (z)A =v T
I, one has the equality L
v
(z)A=I.
Theorem 2.5 LetLbe a space of classV and letv 2 C n
,J k
2 Lsatisfy (2.13). LetP k
be the nnmatrices defined by the identities e T k P s = e T s J
kand satisfying the equality P v k P k =I.
Assume thatLis a matrix algebra closed under conjugate transposition.
(i) We have B = n X k=1 (trJ k ) P k : (2:14) (ii) Ifv k =trJ k, i.e. [trJ 1 trJ n ℄J k =e T k ; k=1;:::;n; (2:15) then fJ k
(iii) IfLis commutative, i.e.J i J j =J j J i, 8i;j, thenJ k =P kand B= n X k=1 (trJ k ) J k ; (2:17) so both Band B 1 are matrices ofL.
Proof. Exploit the definition ofB to obtain the equality[B℄ ij = P n r=1 [J j J i ℄ rr. The
closure under conjugate transposition and under multiplication ofL implies thatJ j J i = P n k=1 a k J k for some a k
2C. Finally, by condition (2.13), one hasa k =[J i ℄ jk =[ P k ℄ ij,
and the representation ofB in (2.14) is proved. Assertions (ii) and (iii) follow easily from
assertion (i).
As it is shown in the following Example 3 in the case L = , the computation of =B
1
can be simplified by using the information onBfound in Theorem 2.5.
Example 3. In solving the exercise of Example 1, one observes that
B = 2 6 6 6 6 4 5 0 3 0 1 0 8 0 4 0 3 0 9 0 3 0 4 0 8 0 1 0 3 0 5 3 7 7 7 7 5 ; B 1 = 1 12 2 6 6 6 6 4 3 0 1 0 0 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 0 0 1 0 3 3 7 7 7 7 5 : (2:18)
Theorem 2.5(iii) for J k
= (e
k
) together with (2.8) and (2.18) allows to deduce the
explicit form ofBandB 1
for generic values ofn:
B =nJ 1 +(n 2)J 3 ++ J n nodd 2J n 1 neven ; B 1 = 1 2n+2 (3J 1 J 3 ):
The inverse ofBis obtained from the equality 1
2n+2
[30 10 0℄B =e T
1
and from Lemma 2.4. Thus an expression of Afor ngeneric is obtained: A = 1 2n+2 h (3 1 3 )J 1 + P n 1 k=2 (2 k k 2 k+2 )J k + (3 n n 2 )J n i ; k =(J k ;A): (2:19)
If the space L is such that there exist and can be easily computed matrices J k
2 L
satisfying the condition (2.15), thenL
Ais simply given by its Fourier expansion L A = n X (J k ;A)J k : (2:20)
Example 4. The three matrices of the algebra J 1 = 1 p 8 2 4 1 1 1 1 0 1 1 1 1 3 5 ; J 2 = 1 p 8 2 4 1 0 1 0 2 0 1 0 1 3 5 ; J 3 = 1 p 8 2 4 1 1 1 1 0 1 1 1 1 3 5 (2:21)
satisfy the identities
v T J k =e T k ; k =1;2;3; wherev T = [trJ 1 trJ 2 trJ 3
℄. So, by Theorem 2.5(ii), they define an orthonormal basis
of . Thus, forn=3, an expression of
Aalternative to (2.19) holds: A =(J 1 ;A)J 1 +(J 2 ;A)J 2 +(J 3 ;A)J 3 ; J k = v (e k ):
The matrices (2.21) can be obtained also by applying the Gram-Schmidt procedure to the three matrices
M 1 = 2 4 1 1 1 1 0 1 1 1 1 3 5 ; M 2 = 2 4 2 z 1 z z 1 z 2 1 z z 1 z 2 z 3 5 ; M 3 = 2 4 x+2y 4 y x y 2x+2y 4 y x y x+2y 4 3 5 : In fact, M 1 = p 8 J 1 ; M 2 (J 1 ;M 2 )J 1 = p 8J 2 ; M 3 (J 1 ;M 3 )J 1 (J 2 ;M 3 )J 2 = p 8J 3 :
Problem 3: Is it possible to define via (2.15) an orthonormal basis of for alln?
Problem 4: Under what assumptions onL 2 V there exist matricesJ k in Lsatisfying the conditions (2.15)? The representation (2.17) ofB = ((J i ;J j )) n i;j=1
holds under assumptions less restric-tive thanJ i J j =J j J i,
8i;j. Consider, in fact, a setfJ 1 ; J 2 ;:::; J n gof linearly
indepen-dent matrices (not necessarily spanning aVspace). Then, by the definition ofB,
[B℄ ij = n X r;s=1 [J i ℄ rs [J j ℄ rs = n X r;s=1 [J i ℄ sr [J j ℄ rs = n X s=1 [J i J j ℄ ss :
Thus the identity B = P n k=1 (trJ k ) J k holds iff tr(J i J j ) = tr P n k=1 [J k ℄ i;j J k . In particular, the latter condition is satisfied if
J i J j = n X [J k ℄ i;j J k ; 1i;j n: (2:22 1 )
Now, (2.22 1
) together with the condition
I = n X k=1 v k J k ; for somev k 2C; (2:22 2 ) implies thatv T J k = e T k ,v = [v 1 v 2 v n ℄ T , i.e. L = SpanfJ 1 ;:::;J n gis a member
ofV. The following Theorem 2.6 proves that the conditions (2.22*), or, equivalently, the
assumptionL=*space [30], imply several other properties onLandL A.
Theorem 2.6 Assume that n linearly independent nn matrices J 1
;:::;J
n satisfy the
conditions (2.22*). Then the *spaceL=SpanfJ 1
; J
2 ;:::; J
n
ghas the following
proper-ties: (i)v T J k =e T k ,k =1;:::;n, where P n k=1 v k J k =I; i.e.L2V.
(ii)Lis a matrix algebra.
(iii)Lis closed under conjugate transposition.
Moreover, we have: (iv) IfB =((J i ;J j )), then B= n X k=1 (trJ k ) P k = n X k=1 (trJ k ) J k (2:23) i.e. Band B 1 are inL. (v) If k =(J k ;A)andz2C n , thenz L v ( )z= P n k=1 [P k z℄ A[P k z℄. (vi) IfA=A , thenL A =L A
andmin(A)(L A
)max(A). In particular, Ahermitian positive definite )L
Ahermitian positive definite
: (2:24)
Proof. See [30].
Problem 5: Is it possible to extend the class of spacesLfor which (2.24) holds? (Notice
thatLmust be at least closed under conjugate transposition.)
Group matrix algebras represent an important class of *spaces. Before [30], it was known that ifL = C fcirculantsg, then the matrix L
T T
T,
T =Toeplitz non singular,
inherites positive definiteness fromT T
T. Now, after [30], we know that this is true for any,
commutative or non commutative, group matrix algebra L. Moreover, the following
ex-ample shows that computingL T
T
T,
L=fdihedral group matricesg, is not more expensive
than computingC T
T
T.
Example 5 (Appendix notation). In the Appendix it is shown that ifT =(t i j
) n 1
i;j=0
is a generic Toeplitz matrix andI(e
r
)is the Toeplitz matrix with[I(e r )℄ 0k =Æ kr, [I(e r )℄ k0 =0,
then all inner products (I(e r );T T T), (JI(e r );T T T), (I(e r ) T ;T T T), (JI(e r ) T ;T T T), r=0;:::;n 1;where J = 2 6 6 6 6 6 6 6 4 0 0 1 .. . . .. 1 0 .. . . .. . .. . .. ... 0 1 . . . .. . 3 7 7 7 7 7 7 7 5 ; (2:25)
can be computed withO(nlogn)arithmetic operations (see also [41]). As a consequence,
the time complexity of the computation of the Fourier coefficients k = (J k ;T T T) in equality C T T T = P k J k, J k = C( 1 p n e k
) (see (2.11)) is at mostO(nlogn). However,
the same result holds in computing k = (J k ;T T T) in D T T T = P k J k, where J k = D( 1 p n e k
)represent the obvious (orthonormal) basis of the dihedral group algebra
D= X JY JY X :X;Y n 2 n 2 circulants :
The proof is based on the equality
T T T = T T 1 T 1 +T T 3 T 3 T T 1 T 2 +T T 3 T 1 T T 2 T 1 +T T 1 T 3 T T 2 T 2 +T T 1 T 1 ; whereT iare the n 2 n 2
Toeplitz matrices defined by
T = T 1 T 2 T 3 T 1 ;
and on the remark that the matrices J
kcan be written in terms of matrices I(e r ),JI(e r ), I(e r ) T ,JI(e r ) T of ordernand n 2
(the details are left to the reader).
There is a class of *spaces which is associated with the set of thennunitary matrices.
More precisely, if thennmatrixU is such thatU
=U 1
, then the commutative matrix algebra L=sdU :=fUd(z)U :z2Cg ; d(z) =diag (z 1 ; z 2 ;:::; z n );
is a *space, and thus all conclusions in Theorem 2.6 hold [30]. A collection of useful results onL
Aand on its properties when
L=sdU, is given in the following
Theorem 2.7 LetU be annunitary matrix and letL=sdUbe the space of all matrices
simultaneously diagonalized byU. LetL A
=Ud(z
A )U
denote the best l. s. fit toAinL.
Then (i) IfA=A thenL A =L A and min(A)(z A ) i max(A) (ii) L
A is hermitian positive definite whenever A is hermitian positive definite. If, in
particular, Lis spanned by real matrices, thenL
Ais real symmetric positive definite (pd)
whenever A is real symmetric positive definite (pd). (iii)L A =Ud(z A )U ,(z A ) i =(U AU) ii, i=1;:::;n. (iv)z xy T =d(U x)U T y,x; y2C n . (v)trA=trL A.
(vi) IfAis hermitian positive definite, thendetAdetL A.
Proof. The representation in (iii) is a simple consequence of the equalitykUd(z)U Ak F = kd(z) U AUk
from theL
Arepresentation in (iii). Items (iv), (v) and (vi) follow from (iii). In particular, if Ais hermitian positive definite, then, by the Hadamard inequality, we have
det(L A )=detd(z A )det(U AU)=det(A):
A very useful representation ofL A,
L=sdU, is obtained by exploiting the fact thatL
is inV. In fact, for anyv 2C n
such that[U T
v ℄
i
6=0,8i, the matrices of the spaceLcan
be represented as L v (z)=Ud(U T z)d(U T v ) 1 U ; z2C n (2:26)
(see Proposition 2.4 in [30]). So, given a vectorv 2 C n such that [U T v ℄ i 6= 08i, if the v-row ofL A, i.e. v T L A, is given, then L A =Ud(U T L A T v )d(U T v ) 1 U =Ud(U T B 1 )d(U T v ) 1 U (2:27)
where the latter identity holds if the basisJ kof Lis defined byJ k =L v (e k ).
Example 6. At the beginning of the next Section 3 it is shown that the matrix algebras
Cand aresdU spaces, i.e. satisfy the identities C=sdU
C
; =sdU
;
for suitable unitary matricesU Cand
U
known as Fourier and sine transform, respectively.
Thus the following representations ofC Aand Ahold: L A =U L d(U T L B 1 )d(U T L e 0 ) 1 U L ; L=C; (J k =L(e k )) (2:28)
(alternative to (2.11) and (2.19)) which let one reduce computations involvingC Aand
Ato
fast Fourier and sine discrete transforms, respectively (computable inO(nlogn)arithmetic
operations).
3
L Aas a Preconditioner (
A= T,
A = T T Twhere
Tis Toeplitz)
Because of the structure of transforms and related algebras involved in the present section, it is convenient to introduce a general setting for diagonal spacesLwhere one can retrieve
the vector zdefining the information sufficient to define a matrix A 2 L. This vector z
is equal to a linear combination of the rows ofA, that isz T
= v T
A, where for the most
known algebras (circulant, , Hartley, Hessenberg) v T = e T 0 = [100℄. To recall that a matrixA 2Lis defined byz T =v T
Aone can use the symbolL v
(z)instead ofA(see
[30] or the previous section), and, in particular, the symbol L(z) ifv = e
0. In order to
follow the notation in [10], suitable for fast transforms, the indeces in this section and in the Appendix will run from0ton 1(instead from1ton).
Let U
L be a unitary matrix and let
L be the space of all matrices simultaneously
di-agonalized by U L, i.e. L = sd U L = fU L d(z)U L : z 2 C n g, d(z) = diag (z k ;k = 0;:::;n 1). Choose a vectorv2C n
so that the matrix
L v (z)=U L d(U T z)d(U T v ) 1 U (3:1)
is well defined. Notice thatv T L v (z) =z T
. Thus, any matrixAofLis determined by the
vectorv T
A, thev-row ofA. Ifv=e 0, then
A2Lis determined by its first row.
The formula (3.1) holds in particular forL=C 1
=the space ofnn(1)-circulant
matrices. Any(1)-circulant matrix is determined by its first rowz T =[z 0 z 1 z n 1 ℄ T , z k
2C, via the formula
C 1 (z)= n 1 X k=0 z k P k 1 ; P 1 = 2 6 6 6 4 0 1 . .. 1 1 0 3 7 7 7 5 : (3:2) To see that C
1 can be put in the form (3.1) set v = e 0, U C 1 = F andU C 1 = DF, whereD =diag (e ij=n ;j=0;:::;n 1),i= p
1, andF is the Fourier matrix F = 1 p n (e i2ij=n ) n 1 i;j=0
(prove (3.1) first for z = e
1 and use (3.2)). Moreover, if
L is the Jacobi algebra of
Section 2, equivalently defined as the set of all matrices X = (x ij ) n 1 i;j=0 satisfying the cross-sum condition x i 1;j +x i+1;j =x i;j 1 +x i;j+1 (3:3) withx i; 1 =x 1;i =x i;n =x n;i
=0, then one can prove that (3.1) holds forv =e 0and U = q 2 n+1 (sin (i+1)(j+1) n+1 ) n 1 i;j=0 . Now letC S 1and C SK
1 be, respectively, the spaces of all symmetric and skewsymmetric (1)-circulant matrices, i.e.
C S 1 =fX 2C 1 : X T =Xg; C SK 1 =fX2C 1 :X T = Xg;
and let casxdenote the function osx+sinx. The Hartley matrix is defined by
H = 1 p n cas2ij n n 1 i;j=0 :
The discrete Hartley transform of a vector z, Hz, is computable inO(nlogn)
arith-metic operations (a.o.), i.e. has the same computational complexity of the discrete Fourier transformFz(see [13], [45]). Note thatH=U
Hwith H=C S 1 +JP 1 C SK 1 whereJ is the
reversalnnmatrix, i.e.[J℄ ik
=Æ
i;n k 1[9].
The matrix H can be naturally included in a set of eight Hartley-type (Ht) matrices
[10]: H; HI T ; K T = 1 p n (cas (2i+1)j n ) n 1 i;j=0 ; K T I ; K ; KI T ; G= 1 p n (cas (2i+1)(2j+1) 2n ) n 1 i;j=0 ; GI (3:4) where I = 1 p 2 2 6 6 6 4 p 2 I b n 1 2 J b n 1 2 p 2 J b n 1 I b n 1 3 7 7 7 5 ; I = 1 p 2 2 6 4 I b n 2 J b n 2 p 2 J b n 2 I b n 2 3 7 5 :
In the above definitionsI k(
J
k) is the identity (reversal) matrix of order
k; moreover the
presence of the central row and column including
p
2depends on the oddness ofn.
EachHttransform can be reduced to a Hartley transform. In fact, ifR Kand
R
are the nnsymmetric orthogonal matrices
R K =diag ( os k 2 )+diag (sin k 2 )JP 1, R =diag ( os ' k 2 )+diag (sin ' k 2 )J, where k = 2k n ,' k = (2k+1) n ,k =0;:::;n 1, then K T =HR K ; G=R K T : However, Htradix-n
2 splitting formulas hold for each
HttransformU = U n 1 n 2 and lead to factorizations ofU n, corresponding to factorizations of
n, in terms of sparse
orthog-onal matrices [10]. TheHtradix-2splitting formulas are reported in the following
Proposition 3.1 [10] LetQ
n;2be the even-odd (
2-stride) permutation matrix defined by
Q n;2 z=[z 0 z 2 z 2n 2 z 1 z 3 z 2n 1 ℄ T ; z2C 2n : (i) ForU =H; K T , we have U 2n = 1 p 2 I X I X U n 0 0 U n Q n;2 ; whereX =R Kfor U =HandX =R for U =K T . (ii) Set R =diag ( os ' k 4 )diag(sin ' k 4 )J; ~ R =diag ( os k 4 )diag (sin k 4 )JP 1 : ForU =K ; G, we have U 2n = 1 p 2 X Y YW XW U n 0 0 U n Q n;2 ; whereX =R +, Y =R ,W =J forU = Gand X = ~ R +, Y = ~ R ,W =JP 1 for U =K.
The set of matrix algebrasL=sdU L,
U
L
=Ht, can be also obtained:
H=sdH=C S 1 +JP 1 C SK 1 ; =sd(HI T )=C S 1 +JP 1 C S 1 ; Æ=sdK T =C S 1 +JC SK 1 ; =sd(K T I )=C S 1 +JC S 1 ; K=sdK =C S 1 +JP 1 C SK 1 ; =sd(KI T )=C S 1 +JP 1 C S 1 ; =sdG=C S 1 +JC SK 1 ; =sd(GI )=C S 1 +JC S 1 : (3:5)
Notice that the equality (3.1) holds for with v 6= e
0 [30] since the condition [G T e 0 ℄ i
The algebrasH, ,Æ,,K, , ,represent theHtcounterpart of the set of eight
Ja-cobi algebras (including ) considered in [38]. However matrices from Jacobi algebras are
polynomials in a symmetric tridiagonal matrix, whereas no simple nonderogatory matrix generating Htis known [23], [10]. The algebras listed in (3.5) can have different effects
in a number of applications, including displacement decompositions, preconditioning tech-niques and newtonian algorithms for unconstrained minimization. SomeHtalgebras have
been used in displacement and Bezoutian theory, i.e. as the factorsM i, N i in matrix rep-resentations A = P M i N i [23], [4], [22], [33], [34]. For
A equal to the inverse of a
Toeplitz-plus-Hankel (T +H) matrix, the latter representations are the basis of efficient
directT+Hlinear systems solvers. In [33], [34] the matricesH,K,K T
andGare named H I ,H II ,H III andH IV
, respectively, and are used to represent Toeplitz-plus-Hankel Be-zoutians. TheLQN minimization methods, recently introduced in [25], have been initially
implemented forL = H =Hartley algebra [26], [11]. Notice that the fourHttransforms H,K,K
T
andGhave been introduced independently in [35].
The Htalgebras Hand K, , have been exploited in [9], [37] and in [30],
respec-tively, to define preconditioners in solving positive definite Toeplitz systems Tx = b, T = (t
ji jj )
n 1
i;j=0
, by the conjugate gradient (CG) method. It has been noticed that such
preconditioners, which are the best l.s. fitsH T, K T, T and T, approximate T better than
the T.Chan-Huckle fit(C 1
)
T [18], [36]. In fact, the latter matrix, (C
1 )
T, is a symmetric (1)-circulant matrix andHtincludes, by definition, symmetric(1)-circulant matrices.
Moreover, amongHt,andyield the best approximations ofT[30]. The latter remark is
essentially based on the fact thatandare the onlyHtalgebras which are simultaneously
symmetric and persymmetric likeT. So, one obtains the inequalities (2.12) (C=C 1) and k T Tk F kK T Tk F k(C 1 ) T Tk F (3:6)
which justify the use ofHtmatrices as preconditioners.
The following theorem reports explicit formulas for(C 1 ) T, K T and T ( neven), and
states that, at least for a class of positive definite Toeplitz matrices T, the eigenvalues of L
1
T
T,L =C 1
;K ;, are clustered around1. It follows (see [1], [2]) that such matrices L
T can be efficiently used as preconditioners of
Tx=b. Analogous results hold forL=C
[16],L=H[9],L=[30]. Theorem 3.2 [30] a) LetT =(t ji jj ) n 1 i;j=0
be a symmetric Toeplitz matrix. Sets i =t i + t n i, i = 0;:::;n 1(t n = t 0), and a i = t i i n s i, i = 0;1;:::;n 1. Notice that s i =s n i, a n i = a i. Moreover, if nis even, set b 2k = 2 n P b n 4 j=k+1 s 2j 1 +t n=2 Æ n=2;o ; k =0;1;:::;b n 4 ; b 2k 1 = 2 n P d n 4 e 1 j=k s 2j +t n=2 Æ n=2;e ; k =1;:::;d n 4 e; b n j = b j ; j=1;:::; n 2 1; n 2 whereÆ n=2;e(o)
=1, ifn=2is even (odd), andÆ n=2;e(o)
=0, ifn=2is odd (even). Then
L T =U L d(U T z)d(U T e 0 ) 1 U (3:7)
where, fori=0;:::;n 1, z i = 8 < : a i L=C 1 a i + s i n L=K a i +b n i 1 L=; neven: b) Ifft j g +1 j=0
is a sequence of real numbers satisfying
P jt j j<+1andT (n) is the Toeplitz matrixT (n) = (t ji jj ) n 1 i;j=0
, then the eigenvalues ofL T (n) T (n) , L = C 1, K, , are
clustered around zero, i.e. for any fixed",9k "and ", " k ", such that 8n> "at least n k "eigenvalues of L T (n) T (n)
are in the interval( ";").
Moreover, if P t jjj e ij >0,8 2[ ;℄, thenT (n) andL T
(n) are pd, and the
eigen-values ofI L T (n) 1 T (n)
are clustered around zero.
In the remaining part of this section L A,
L = Ht, is proposed as a preconditioner of CGin the case of non symmetric Toeplitz linear systems.
A way to solve the linear system
Tx=b; detT 6=0;
whereT is a generic (possibly nonsymmetric)nnreal Toeplitz matrixT =(t i j ) n 1 i;j=0 andb 2 R n
, is to apply theCGmethod to the normal equationsT T
Tx=T T
bor, more
generally, to the preconditioned system
(TE T ) T (TE T )y=(TE T ) T b; E T x=y (3:8)
whereEis a nonsingular matrix.
The CG method applied to (3.8) will be called CGP method, with P denoting the
preconditioning matrixEE T
. In fact, the coefficient matrix in the system (3.8) is similar toP
1
T T
T for anyEsuch thatEE T
=P. Thus it is the choice ofP that influences the
distribution of the eigenvalues ofE 1 T T TE T = (TE T ) T (TE T
) and therefore the
rate of convergence ofCGapplied to (3.8) [1], [2], [16], [30].
At each step theCGP method requires two matrix vector products,TzandT T
w
(be-sides a small number of inner products of complexityO(n)). These computations can be
performed withO(nlogn)a.o., either by using the identities Tz z 0 =C(t) z 0 = p 2n ^ Fd( ^ Ft) ^ F z 0 ; T T w w 0 =C(t) T w 0 = p 2n ^ Fd( ^ J ^ P 1 ^ Ft) ^ F w 0 ;
whereC(t)is the circulant matrix with first rowt T =[t 0 t 1 t n+1 0 t n 1 t 1 ℄and ^ F, ^ J, ^ P
1are the Fourier, the
J and theP
1 matrices of dimension
2n(see (2.25) and (3.2)),
or by using the procedures in [41], [32], [38] in terms of real transforms only. Moreover, in
CGP a systemPz=wneeds to be solved.
ClearlyCGP is well defined and more efficient thanCGapplied to the linear system T
T
Tx=T T
b(which is in general outperformed by direct methods, having a slow rate of
1. P is pd (i.e. real symmetric positive definite);
2. P is computable in at mostO(nlogn)a.o.;
3. Pz=wis solvable in at mostO(nlogn)a.o.;
4. the spectrum ofP 1
T T
T is more “clustered” than the spectrum ofT T
T.
Intuitively, in order to obtain the property 4, the matrix P should be a good
ap-proximation of T T T. In this section P = L T T T, i.e.
P is the best least squares fit
to T T
T from suitable subspaces L of C nn
. This choice of P is suggested in [41]
in the case L is a Jacobi matrix algebra. The matrix L T
T
T is also studied in [14] for L=C C
1
fnncirculantsg. HereL T
T
T is shown to satisfy the conditions 1,2,3 for
five differentHtmatrix algebrasL. However, by the same definition ofHtin terms ofC S
1
andC SK
1 , it will be clear that the latter result can be extended to all eight
Ht. InvolvingHt
instead ofC
1 is clearly justified since
Htapproximate T T
T better than(1)-circulants.
In fact, because(C 1 ) T T T 2C S 1 , we have kL T T T T T Tk F k(C 1 ) T T T T T Tk F ; L=H ; ;Æ;; kL T T T T T Tk F k(C 1 ) T T T T T Tk F ; L=K ; ; ;: (3:9)
Regarding condition 4, some numerical experiences in Table 1 prove thatCG(Ht) T
T
T
outperforms theCG(I T
T
T
) method and is competitive with CG(L T
T
T
) where L is one
of the more widely exploited algebras C, C
1 and the Jacobi
. Moreover, the general
framework here considered allows us to conclude that the conditions 1,2,3 hold also for spaces Lof matrices which are not simultaneously diagonalized by a unitary matrix. The
latter result is shown in detail in Example 5 of Section 2 whenLis the (non commutative)
dihedral group algebraD. Some related numerical experiments show the efficiency ofDas
preconditioner even for matrices whose structure is not so close to the four–block dihedral frame.
Remark. In [17], [15] the choiceP = C T T C T ( E = C T T ) is suggested, whereC T is the
best l.s. fit toT from the space of circulant matricesC:
C T = 1 n n 1 X k=0 [(n k)t k +kt n k ℄P k 1 :
However, for both Jacobi and Htmatrix algebras L the choice P = L T T L T is not recommended sinceL T is symmetric, even if
T is not (for the Jacobi case see [41]).
Let us restrict the attention to spacesL =sdU
L, where U
Ldefines a transform
com-putable in O(nlogn) a.o.. Examples of such spaces are C
1, Jacobi [46] and
Ht. By
Theorem 2.7(ii), the condition 1 is satisfied for P = L T T T, L = C 1 ;Jacobi;Ht. The
conditions 2 and 3 are satisfied forP = L T
T
T provided that the vector
ain the equality L T T T =U L d(a)U L
is computable in at mostO(nlogn)a.o.. The fast computation ofais
shown by Potts and Steidl [41] in the Jacobi case. Here we extend the result to theHtcase
and give explicit formulas fora. To this aim an expression for the vectoramore convenient
thana=([U T T TU L ℄ kk ) n 1
Recall that ifA is a genericnnmatrix,v 2 C n is such that[U T L v ℄ i 6= 0,8i, and J k =L v (e k ),L=sdU L, then L A =U L d(a)U L ; a=d(U T L v ) 1 U T L B 1 : (3:10)
In the following we give procedures for the computation ofB 1 in (3.10) in the cases L = , v = e 0, and L = , v = e 0 +e
n 1. The latter choice of
v is justified by the
fact thatA 2 is always determined by its e 0 +e n 1-row ( [U T (e 0 +e n 1 )℄ i 6= 0, 8i),
whereas there are values of n for which e T
0
A, A 2 , does not define A (some entries [U T e 0 ℄ i =[G T e 0 ℄
iare zero for
n=6+4r). We also give explicit formulas forB 1 ,L2 fC 1 ;H ;K ;;g,J k = L(e k
). The above procedures and formulas can be implemented
inO(n)a.o., provided that a fixed set of vectorsr A, ~ r A, h A, ~ h
Ais known. The components
of such vectors are the inner products
r k;A =(I(e k );A); ~r k;A =(I(e k ) T ;A); h k;A =(JI(e n 1 k ) T ;A); ~ h k;A =(JI(e n 1 k );A); (3:11)
k=0;:::;n 1, whereI(z)is the upper triangular Toeplitz matrix with first rowz T I(z)= 2 6 6 6 6 4 z 0 z 1 z n 1 0 z 0 . .. .. . .. . . .. ... z 1 0 0 z 0 3 7 7 7 7 5 (3:12) (I(e n )=0). Observe that r A =~r JAJ =~r A T; ~r JA =Jh A ; h A = ~ h JAJ = ~ h JA T J : (3:13)
IfAis generic, one needs to performO(n 2
)a.o. in order to compute the components
in (3.11). However, by Lemma 5.1 in the Appendix, ifA=T T
T whereT is Toeplitz, then r A, ~ r A, h A, ~ h Aare computable in
O(nlogn)a.o.. So, one obtains the next Theorems 3.3,
3.5, and Corollary 3.8.
Computing A
Theorem 3.3 The vectora = d(U T e 0 ) 1 U T B 1 in the equality A =U d(a)U , = C S 1 +JC S 1, A=T T
T, is computable in at mostO(nlogn)a.o.. So, the conditions 1, 2, 3
on preconditionersP ofT T
T are satisfied forP = T
T
T.
Let us give a procedure for the computation of B 1 , J k = (e k ). The matrix B 1
was computed in [30] by using the remark thatB 1
2(Theorem 2.6(iv)). In fact, if
T 1;1 0;0 = 2 6 6 6 6 6 6 4 0 1 1 1 0 1 1 . .. ... . .. 0 1 1 1 0 3 7 7 7 7 7 7 5 ; e= 2 6 6 6 6 6 6 6 4 1 0 1 0 1 .. . 3 7 7 7 7 7 7 7 5 ; o= 2 6 6 6 6 6 6 6 4 0 1 0 1 0 .. . 3 7 7 7 7 7 7 7 5 ; (3:14)
andBdenotes the matrix((L(e i );L(e j ))) n 1 i;j=0 ,L2f;g, then B 1 = 1 2n 2IJT 1;1 0;0 1 n 2 ee T +oo T J(eo T +oe T ) (3:15)
where the upper and lower signs refer, respectively, to the casesL=andL=[30]. The
matrix vector productB 1
can be clearly calculated inO(n)a.o.. Thus, Theorem 3.3 is
proved if the vector is computable inO(nlogn)a.o. forA=T T T. A direct computation of =((J k ;T T T)) n 1 k=0
is not recommended because the matrices
J
k
= (e
k
) are not sparse. For example, by using the cross-sum conditions (3:3) with x 1;n 1 k = x k;n = x n;k = x n 1 k; 1 = x 0;k(satisfied by any matrixX [30]), one
can write(e n
4
) and realize that it has n
2
4
nonzero entries. In Lemma 3.4 we introduce a basis fJ 0 k g of = C S 1 +JC S
1 where each matrix J
0
k
can be written in terms of a constant number of matricesI(e
k ),I(e k ) T ,JI(e n 1 k ) T ,JI(e n 1 k ). The basisfJ 0 k gis obtained
by grouping together the obvious basis ofC S
1
andJC S
1
and by omitting the surplus. As a consequence, by Lemma 5.1 of Appendix, the vector
0 =((J 0 k ;T T T)) n 1 k=0 is computable inO(nlogn)a.o.. The next Lemma 3.4 also provides some relations between fJ
0
k gand fJ
k
gwhich imply that is computable from 0
inO(n)a.o.. So, Theorem 3.3 is proved.
Fork =0;1;:::;nset Z k =I(e k )+I(e k ) T +I(e n k )+I(e n k ) T (3:16) (I(e n ) = 0). Notice thatZ 0 = 2I, Z 1 = T 1;1 0;0 , Z j = Z j 1 Z 1 Z j 2, j = 2;:::;n.
Moreover, the set fA k g b n 2 k=0 , A 0 = 1 2 Z 0 = 1 2 Z n, A k = Z k = Z n k, 1 k b n 1 2 , A n 2 = 1 2 Z n 2
(neven), is the obvious basis ofC S
1.
Lemma 3.4 [31] The set ofnnmatricesfJ 0 k gwhere J 0 k = A k 0kb n 2 JA k b n 2 1 b n 2 +1kn 1 (3:17)
form a basis of. Moreover the basisfJ k
g,J k
=(e
k
), can be expressed in terms of the J
0
k
by the following identities:
J k = 8 > > < > > : J 0 0 =I k =0 J k 2 +J 0 k J 0 k+b n 2 1k b n 1 2 (J 1 =0) J 0 k k = n 2 (neven) J n k +J 0 n k b n 2 +1kn 1: (3:18)
Thus, for the vectors =((J k ;A)) n 1 k=0 and 0 =((J 0 k ;A)) n 1 k=0 we have k = 8 > > < > > : 0 0 =trA k =0 k 2 + 0 k 0 k+b n 2 1k b n 1 2 ( 1 =0) 0 k k = n 2 (neven) n k + 0 b n +1kn 1: (3:19)
Proof. The setS = fA k ;JA k : k = 0;:::;b n 2
g generates . Let nbe odd. Since [ P n 1 2 k=0 A k ℄ ij = 1, 8i;j, we have P n 1 2 k=0 JA k = P n 1 2 k=0 A k and thus JAn 1 2 is a lin-ear combination of the remaining matrices in S. Analogously, if n is even, the identity J( P n 2 k=0;keven A k ) = P n 2 k=0;kodd A k implies that JA n 2 and JA n 2
1 are linear
combina-tions of the other matrices inS. In order to prove (3.18), it is sufficient to verify that the
first row of the matrices on the right hand-side are the vectorse T
k
,0k n 1.
Proof of Theorem 3.3 (in detail). The vectorain the equality T T T =U d(a)U T is
computable inO(nlogn)a.o. by the following steps. Calculate the inner products vectors ~ r T T T =r T T T, h T T T and ~ h T T T =h TT
T by using formulas (5.1) and (5.2) in the Appendix.
ForA=T T T set 0 k = 8 > > > > > > > < > > > > > > > : r 0;A k =0 2(r k;A +r n k;A ) 1k b n 1 2 2r n 2 ;A k = n 2 (neven) h n 1;A = ~ h n 1;A k =b n 2 +1 h n k+b n 2 ;A + ~ h n k+b n 2 ;A + h k b n 2 2;A + ~ h k b n 2 2;A b n 2 +2kn 1: (3:20) Calculate from 0 and then z = B 1
by using, respectively, (3.19) and (3.14),
(3.15). Thena=d(U T e 0 ) 1 U T z . Computing A
Theorem 3.5 The vector a = d(U T (e 0 +e n 1 )) 1 U T B 1 in the equality T T T = U d(a)U , = C S 1 +JC SK 1, is computable in at most
O(nlogn) a.o.. So, the
condi-tions 1, 2, 3 on preconditionersP ofT T
T are satisfied forP = T
T
T.
Let us give a procedure for the computation ofB 1 ,J k = e 0 +e n 1 (e k ). Since the matricesJ
k are dense and
8nhave not a simple explicit structure, a direct computation of B
1
and is not recommended. However, the existence ofJ
kallows us to obtain a simple
expression ofB 1
in terms of a suitable vectorB 0 1 0 whereB 0 1 , 0 andB 0 1 0 are easily computable.
Lemma 3.6 The set ofnnmatricesfJ 0 k gwhere J 0 k = I k =0 C 1 (e k e n k ) 1kd n 2 e 1; (3:21 1 ) J 0 d n 2 e +k = JC 1 (e k+1 +e n k 1 ) 0kd n 2 e 2 JC 1 (e n=2 ) k=d n 2 e 1(neven) (3:21 2 )
form a basis of . Moreover, the basisfJ 0
k
gcan be expressed in terms of the basis fJ k g, J k = e 0 +e n 1 (e k
), by the following identities:
J 0 k = J 0 +J n 1 k=0 J k J k 1 +J n k 1 J n k 1kd n e 1; (3:22 1 )
J 0 d n 2 e+k = J k+1 J k +J n k 1 J n k 2 0k d n 2 e 2 J n=2 J n=2 1 k =d n 2 e 1(neven): (3:22 2 )
Proof. The obvious basis ofC S 1and JC SK 1 are (3.21 1 ) and (3.212 ), respectively. Since dimC S 1 +dimJC SK 1
=n, the union between (3.21 1
) and (3.212
) is a basis of . In order
to prove (3.22), observe that thee 0
+e
n 1-row of the matrices on the right hand-side are
equal to thee 0
+e
n 1-row of the matrices J 0 k andJ 0 d n 2 e +k . So,fJ 0 0 ; J 0 1 ;:::; J 0 n 1
gis a basis of and, therefore, A = n 1 X k=0 [B 0 1 0 ℄ k J 0 k ; b 0 ij =(J 0 i ;J 0 j ); 0 i =(J 0 i ;A): (3:23) Notice thatB 0 1 = 1 2n (I +e 0 e T 0 +Æ ne e n 1 e T n 1 ), where Æ ne = 1, ifnis even, and Æ ne
= 0, ifnis odd. Thus, the complexity ofB 0 1
0
is determined by the complexity of
0
. By the particular form of J 0 k , if Ais generic, 0 is computable inO(n 2 )a.o. and, if A=T T
T, inO(nlogn)(see Lemma 5.1 of Appendix).
By (3.22) and by the identitiesJ k = e0+en 1 (e k )=Gd(Ge k )d(w )G,w i =(G(e 0 + e n 1 )) 1 i
, the sum in (3.23) becomes
A = [B 0 1 0 ℄ 0 J 0 0 + P d n 2 e 1 k=1 [B 0 1 0 ℄ k J 0 k + P d n 2 e 2 k=0 [B 0 1 0 ℄ d n 2 e+k J 0 d n 2 e+k +Æ ne [B 0 1 0 ℄ n 1 J 0 n 1 = [B 0 1 0 ℄ 0 Gd(G(e 0 +e n 1 ))d(w )G + P d n 2 e 1 k=1 [B 0 1 0 ℄ k Gd(G(e k e k 1 +e n k 1 e n k ))d(w )G + P d n 2 e 2 k=0 [B 0 1 0 ℄ d n 2 e+k Gd(G(e k+1 e k +e n k 1 e n k 2 ))d(w )G +Æ ne [B 0 1 0 ℄ n 1 Gd(G(e n=2 e n=2 1 ))d(w )G: Thus A =Gd(GB 1 )d(G(e 0 +e n 1 )) 1 G with B 1 = T A (e 0 +e n 1 ) = [B 0 1 0 ℄ 0 (e 0 +e n 1 ) + P d n 2 e 1 k=1 [B 0 1 0 ℄ k (e k e k 1 +e n k 1 e n k ) + P d n 2 e 2 k=0 [B 0 1 0 ℄ d n 2 e +k (e k+1 e k +e n k 1 e n k 2 ) +Æ ne [B 0 1 0 ℄ n 1 (e n=2 e n=2 1 ) i.e.B 1 is computable fromB 0 1 0
inO(n)a.o.. This proves, in particular, Theorem 3.5.
Explicit formulas for(C 1 ) A, A, A, H A, K A,
The procedures illustrated above to compute L
Aare essentially based on
representa-tions of B 1 in terms of 0 (L = ) or in terms of B 0 1 0 (L = ), where the J 0 k, defining B 0 and 0
, are the sum of a constant number of I(e k ), I(e k ) T , JI(e n 1 k ) T , JI(e n 1 k
) matrices. In the following Theorem 3.7 we give explicit formulas for L A, L=C
1 ;C
1
;;;H ;K. These formulas have been introduced heuristically and then
rigor-ously proved. Notice that only(C 1
)
Theorem 3.7 The best l.s. fit toA2C nn fromL2fC 1 ;H ;K ;;gcan be represented as L A =U L d(U T L z)d(U T L e 0 ) 1 U L ; (3:24) withz=B 1 ,J k =L(e k ), equal, respectively, to f A = 1 n (r A JI(e 1 )~r A ); 1 2 (f A +f A T )+ 1 2n [(IJI(e 1 ))h A (I(e 2 ) T I(e 1 )J) ~ h A (h 0;A ~ h n 2;A )e 0 ℄; 1 2 (f A +f A T )+ 1 2n (I I(e 1 )J)(h A + ~ h A ) 1 n 2 ee T +oo T J(eo T +oe T ) I 1 2 (r A +~r A );
where the upper and the lower signs refer to the casesC 1 ;H ;andC 1 ;K ;, respectively, and I 1 2 = diag ( 1 2 ;1;:::;1), e = [1 0 1 0℄ T , o = [0 1 0 1℄ T . Moreover, for L=;, L A =(C 1 ) A+A T 2 +J(C 1 ) JA+AJ 2 +JR ; R2C S 1
whereR=0ifL=andnis even.
Proof. Compute the vector B 1 for J k = L(e k ). For example, ifL = C 1, then J k = P k 1 . Therefore [B 1 ℄ k = 1 n (P k 1 ;A) = 1 n (r k;A r~ n k;A
). The formulas for L =;are essentially obtained by rewriting in vectorial form some analogous results in
[30]. The formulas forL = H ;Kare new (in [9] only the formula for H T,
T symmetric,
is obtained). In order to prove the equality involving (C 1
)
JA+AJ
2
, observe that the latter matrix belongs toC
S
1and use (3.13).
It is clear, from Theorem 3.7, that the vectorB 1
is computable inO(n)a.o. provided
that the inner products in (3.11) are given. Then, the crucial remark in the analysis of the complexity ofCGP method withP =(Ht)
T T
T (conditions 2 and 3) is that the
computa-tion in (3.11) can be performed in at mostO(nlogn)a.o.. More precisely, forA =T T
T
the formulas in Theorem 3.7 can be simplified by observing thatT T
T is symmetric andT
is persymmetric (JT = T T
J), and therefore, by (3.13), the identities~r T T T = r T T T and ~ h T T T = h TT
T hold. Finally, the fact thatT is Toeplitz allows us to apply Lemma 5.1 of
Appendix and state the following Corollary 3.8 The vectora = d(U
T L e 0 ) 1 U T L B 1 in the equalityL T T T = U L d(a)U L , L=C 1
;H ;K ;;, is computable in at mostO(nlogn)a.o.. So, the conditions 1, 2, 3 on
preconditionersP ofT T
T are satisfied forP =(C 1 ) T T T, H T T T, K T T T, T T T, T T T. Experimental results
We have applied theCG(L T T T )method,L=I;;H ;C; ;C 1 ;K ;;D, to the system Tx=b =[11 1℄ T
for five different choices of the matrixT. The results are reported
in Table 1. IfLis the Jacobi algebra , then
Acan be expressed by (3.24) with
L= and z= 1 (3e 0 e 2 ) 1 ; =r A +~r A I(e 2 ) T (h A + ~ h A ) (3:25)
Table 1: Performance ofL T T T preconditioners L T I T II T III T IV T V I 148 184 >128 >512 23 22 46 89 69 198 24 23 73 283 6 6 10 10 41 78 H 23 22 99 445 6 6 7 9 38 70 C 17 19 94 453 6 6 8 9 33 63 21 23 29 63 5 4 14 16 43 75 C 1 18 19 94 446 6 6 11 14 35 65 K 26 23 93 439 6 6 13 15 41 76 26 25 71 269 6 5 13 16 46 80 D 30 30 >128 >512 9 8 13 14 59 132
where is the same matrix (5.3) of the Appendix. This result follows from the expression ofB 1 ,J k = (e k
), found in Example 3 of Section 2. IfLis the dihedral group algebra D, then the first row ofD
T T
T can be computed by the formulas
( [D T T T ℄ 0k ) n 2 1 k=0 = 1 n (I+ ^ JI(^e 1 ))(2r T T 1 T 1 +r T T 2 T 2 +T T 3 T 3 ); ( [D T T T ℄ 0k ) n 1 k= n 2 = 1 n [ h k;T T T +h3 2 n k 2;TT T n 1 k= n 2 I(^e 1 ) ^ Jh T1T T 1 +T3T T 3 h T T 1 T1+T T 2 T2 ℄ (3:26) where ^ J and ^e
1 are the matrix
J and the vector e 1
= [0 1 00℄ T
of dimension n=2
(see Example 5 in Section 2). ByT I,
T
II, T
III we denote the three Toeplitz matrices T
considered in [41] in the points (i), (iii), (iv). The elements of the matricesT IV and T V are defined by t IV 0 =t V 0 =1; t IV k = 1 (k+1) 0:5 ; t V k = 1 jsinkj+1 ; t IV k =t V k = 1 log(k+1)+1 ; k 1:
Table 1 shows the number of steps required to satisfy the stopping criterion
kT T Tx k T T bk kT T bk <10 7 (x 0
= 0) for the two different dimensions n = 128 and n = 512. Notice that the good
performance of preconditioners, pointed out in [21] for T, T = T T , seems to hold also for T T T,
T non symmetric. But Table 1 also shows that circulant and Hartley type
4
An Efficient
L kQN
Algorithm for the Unconstrained
Minimization
In [25] the followingLQN procedure for the minimization of a functionf : R n
! R is
introduced in terms of a subsetLofC nn : x 0 2R n ; B 0 =pd nnmatrix: For k=0;1;::: : 8 > > > > < > > > > : d k = B 1 k g k S L B k 1 g k NS x k+1 =x k + k d k ; k 2AG k s k =x k+1 x k ; y k =g k+1 g k B k+1 ='(L B k ;s k ;y k ) (LQN algorithm)
where pd means real symmetric positive definite, g k = rf(x k ), AG k is the Armijo-Goldstein set AG k =f2R + : f(x k +d k )f(x k )+ 1 d T k rf(x k ) & d T k rf(x k +d k ) 2 d T k rf(x k )g; 0< 1 < 2 <1
[20], and'is the Hessian approximation updating function
'(B;s;y )=B+ 1 s T y yy T 1 s T Bs Bss T B: (4:1)
We see that there are two possible definitions of theLQN search directiond
k, in terms of B k and in terms of L B k
. The former leads to a Secant method, since B
k solves the
secant equationXs k 1
=y
k 1. The latter corresponds to a Non Secant one ( L B k s k 1 6= y k 1). Notice that if B k = L B k (e.g. when L = C nn
), then both S and NS LQN
coincide with theBFGSalgorithm, the well known quasi-Newton optimization procedure
with superlinear rate of convergence [20], [40]. If the setLsatisfies the condition
Bpd ) L Bpd
; (4:2)
then the aboveLQN algorithm is well defined and yields a strictly decreasing sequence f(x
k
)unlessg k
=0for somek. In fact, by the structure of', B kpd ) L B k pd s T k y k >0 ) B k+1 pd ) L B k +1 pd: (4:3) The conditions T k y k > 0is satisfied since k 2AG
k. The fact that B
k+1 and L
B
k +1
are pd guarantees thatd
k+1is a descent direction both in the
Sand in theNScase.
Now assume that L = sd U for some unitary matrix U and L is spanned by real
all vectorsd
kare defined on
R. TheLQN algorithm, written in terms ofU, becomes x 0 2R n ; B 0 =pd nnmatrix; U d 0 = U B 1 0 g 0 S d(z 0 ) 1 U g 0 NS ; d 0 =U(U d 0 ): Fork =0;1;::: : 8 > > > > > > < > > > > > > : x k+1 =x k + k d k ; k 2AG k s k =x k+1 x k ; y k =g k+1 g k (4:4 1 ) (4:4 2 ) S (4:4 3 ) NS d k+1 =U(U d k+1 ) where z k+1 =z k + 1 s T k y k jU y k j 2 1 z T k jU s k j 2 d(z k ) 2 jU s k j 2 ; (4:4 1 ) z kis the vector z B k in the equality L B k =Ud(z B k )U , and U d k+1 = 8 > > > > > > < > > > > > > : d(z 1 k )U g k+1 + s T k g k +1 y T k s k d(z 1 k )U y k + h 1+ (z 1 k ) T jU y k j 2 y T k s k s T k g k +1 y T k s k + (z 1 k ) T d(U T y k )U g k +1 y T k s k i U s k ; (4:4 2 ) d(z k+1 ) 1 U g k+1 : (4:4 3 ) In (4.4),jzj (z 1
) denotes the vector with elementsjz i
j (z 1
i
). We have the following results:
1. Each step of LQN can be implemented by performing two products by U and a
constant number of vector inner products.
2. TheNS version ofLQN has a linear rate of convergence.
3. IfU defines a fast discrete transform (cost ofU z O(nlogn)), thenLQN can
be implemented withO(n)memory allocations andO(nlogn)arithmetic operations
per step.
4. If U is the Hartley transform, U ij = 1 p n ( os 2ij n +sin 2ij n
), then theS version
of LQN shows a satisfactory rate of convergence in numerical experiences. The S LQN method is, in fact, competitive with the limited memory BFGSmethod ( L-BFGS[40]) in solving large scale minimization problems.
The points (1) and (3) follow immediately from (4.41
)-(4.43
). In fact, the two transforms are U g k+1 and U (U d k+1
). The point (2) is proved in detail in [25], [28]. Some
experiments related to the behaviour of the S LQN method cited in (4) are illustrated in
It is essential to notice that the iteration B k+1 = '(L B k ;s k ;y k )is in fact reduced, in
theLQN algorithm, to the updating formula (4.4 1
) involving the eigenvalues ofL B
k and L
B
k +1
only, so that the entire computation runs in terms of single indexed arrays and the space complexity is linear in n. Thus the introduction ofLQN methods has shown that
a significant amount of second order information, contained in the eigenvalues z kof
L
B
k,
can be sufficient to solve efficiently a minimum unconstrained problem of large dimension. In other words, the information content of L
B
k
appears to be sufficiently close toB k in
order to maintain a quasi-newtonian rate of convergence.
In order to improve the LQN performance, a LQN algorithm where the space L is
modified at each step has been recently proposed in [27]. More precisely, in [27] it is considered a spaceL
k
C nn
such that the setfX 2L k : X is pd andXs k 1 =y k 1 g
is not empty andB
k+1is defined by updating a pd matrix of L k : B k+1 ='(A k ;s k ;y k ); A k 2L k and pd: (4:5) An obvious choice of L k isL k = sdU k, where U
kis a unitary matrix satisfying the
inequalities (U k y k 1 ) i (U k s k 1 ) i w i >0; i=1;:::;n; (4:6)
which is equivalent to say that L k
satisfies the secant equation U k d(w )U k s k 1 = y k 1
and is pd. Numerical experiences with A k = U k d(w )U k
in (4.5) (see [27]) show that this criterion (change the spaceLat eachk and chooseU
kin order that (4.6) holds) gives
good performances in comparison with the previousLQN method where Lis fixed. For
large scale problems, however, the choiceA k =U k d(w )U k
does not give good results and the reason is in the fact that the eigenvalues w
i in (4.6) have, in general, no link with the
eigenvalues (U k B k U k )
iiof the best l.s. approximation L
k
B
k
. So, in the same paper [27] it is suggested to setA k =L k B k and t ciaoL k (i.e. U
k) only when the condition (4.6) is not
verified (in order to maintain low the complexity per step).
In the following we try to restore a close relation of the updated matrix A
k with the
Hessian approximationB
k by using an alternative strategy: choose w i as the eigenvalues ofL k 1 B k
, in order to maintain theB
kspectral information, and then choose U
k in order to
satisfy the secant equation U k d(w )U k s k 1 = y k 1, w = (w i
). This operation recalls,
in spirit, the distinction between structure and information content of a matrix [7], [48], [8], [5], [6]: in the split L = Ud(z)U
,U is the same unitary transform for all matrices AofL(i.e. U wstructure), whereaszdefines a particular matrixAin the spaceL(z w
information content). The information contentwregains the correspondent information of B
k, whereas the structure defined by U
k reproduces the fundamental structure of secant
methods.
The Belle Epoque algorithm
The generic step of the Belle Epoque algorithm is the following: () Assume that, at a generic stepk, a positive definite matrixA
k = U k d(w k )U k ,U k
unitary, and two vectorss k, y k, s T k y k
>0, are given. The matrix B k+1 ='(A k ;s k ;y k )=A k + 1 y T s k y k y T k 1 s T A k s k A k s k s T k A k (4:7)
is positive definite. By projecting the equality (4.7) onL k
= sd U
k and exploiting the
linearity of the operatorL B( L B+ C = L B + L
C), one obtains the vector w
k+1of the
eigenvalues of the positive definite matrixL k B k +1 : w k+1 =w k + 1 s T k y k jU k y k j 2 1 w T k jU k s k j 2 d(w k ) 2 jU k s k j 2 (4:8)
where jzj denotes the vector with elements jz i
j. Recall that the eigenvalues (w k+1 ) i of L k B k +1
are related to the eigenvalues0< (k+1) 1 ::: (k+1) n of B k+1by the inequalities (k+1) 1 +:::+ (k+1) r (w k+1 ) i1 +:::+(w k+1 ) ir ; (w k+1 ) i r +:::+(w k+1 ) i n (k+1) r +:::+ (k+1) n ; (4:9)
where the index-vector fi 1
;i
2 ;:::;i
n
g is a permutation of f1;2;:::;ng defined so that (w k+1 ) i1 (w k+1 ) i2 :::(w k+1 )
in (see [44]). In particular, we have 0< (k+1) 1 (w k+1 ) i1 (w k+1 ) s (w k+1 ) in (k+1) n (4:10)
(see also the previous Theorem 2.6(vi)). Now introduce a space L k+1
with an ad hoc structure for the current iteration, i.e. set
L k+1
=sdU
k+1 ; U
k+1unitary such that U k+1 d(w k+1 )U k+1 s k =y k : (4:11)
Then the positive definite matrixA k+1 := U k+1 d(w k+1 )U k+1
solves the secant equa-tion asB
k+1, and has eigenvalues strictly related to B k+1by (4.9) and (4.10). Now set d k+1 = B 1 k+1 rf(x k+1 ) (I) A 1 k+1 rf(x k+1 ) (II) : Sinced
k+1is a descent direction (unless rf(x
k+1
)=0), theAG
k+1set is not empty.
Thus, one can set
x k+2 =x k+1 + k+1 d k+1 ; k+1 2AG k+1 ; s k+1 =x k+2 x k+1 ; y k+1 =rf(x k+2 ) rf(x k+1 )
and observe thats T
k+1 y
k+1 >0.
Finally setk :=k+1and return to ().
Notice that the Belle Epoque search directiond
k+1can be computed by exploiting the
formulas d k+1 = 8 > > > > > > < > > > > > > : U k d(w 1 k )U k g k+1 + s T k g k +1 y T k s k d(w 1 k )U k y k + h 1+ (w 1 k ) T jU k y k j 2 y T k s k s T k g k +1 y T k s k + (w 1 k ) T d(U T k y k )U k g k +1 y T k s k i s k ; (I) U k+1 d(w k+1 ) 1 U g k+1 : (II) (4:12)
It follows that the time complexity per step of the Belle Epoque algorithm is determined by the cost of matrix-vector products of typeU
k
zandU
k z, i.e.
Time complexity =O( ost(U k
z))+O( ost(U
k
z))+O(n):
However, the Belle Epoque algorithm does not work in the present form, since the space
L k+1
in (4.11) may be not defined. Belle Epoque works if (4.11) is replaced by
L k+1
=sdU
k+1 ; U
k+1unitary such that U k+1 d( k+1 ~ w k+1 )U k+1 s k =y k for suitable k+1 >0 and ~ w k+1 =" k+1 w k+1 + k+1 e; (w~ k+1 ) i >0 (4:11 0 ) wheree=[11 1℄ T
. In fact, as it is shown after the Remark 0 here below, a unitary ma-trixU
k+1solving (4.11 0
) exists and is obtained as the product of two Householder matrices. So, the time and space complexity of the working Belle Epoque algorithm isO(n)only.
Notice that the matrixA k+1 =U k+1 d(w k+1 )U k+1
does not maps kinto
y
k. Thus the
Belle Epoque method corresponding to the direction (4.12)-(II), is not secant unlessw k+1 is replaced withz k+1 := k+1 ~ w
k+1. So, a third Belle Epoque algorithm can be defined,
the one corresponding to the search direction
d k+1 = A 0 1 k+1 g k+1 ; A 0 k+1 :=U k+1 d(z k+1 )U k+1 : (III) (4:12) Remark 0. By updatingA 0 k =U k d(z k )U k instead ofA k(i.e. by replacing A k with A 0 k in (4.7), andw kwith z
kon the right hand side of (4.8) and of (4.12),(I) ), one obtains three
alternative versions (I)0
, (II)0
, (III)0
of Belle Epoque. Notice that in (I), (II), (III) the updated matrix has the same eigenvalues ofL
k 1
B
k
, but does not map exactlys
k 1into y k 1. On the contrary, in (I)0 , (II)0 , (III)0
the updated matrix mapss
k 1into y
k 1, but its eigenvalues are
a bit different from the eigenvalues ofL k 1
B
k
.
Consider the following
Problem 4.1 Given a vectorwwith positive entries and two vectorss,y,s T
y>0, find a
unitary matrixU, a scalar >0, and a vectorw~ ="w+e,w~ i
>0, such that
Ud( w)U~
s=y :
LetH(z)denote the Householder matrix corresponding to the vectorz, i.e.
H(z)=I 2 kzk 2 zz ; z2C n (4:13)
(H(0) = I). By using the following lemma (see [27]), one can reformulate Problem 4.1
into a simpler problem.
Lemma 4.2 Given two vectors s;y 2 R n
nf0g, letr; x 2 R n
be such that krkkxk 6= 0,
and the cosine of the angle betweenrandxis equal to the cosine of the angle betweens
andy, i.e. r T x = s T y =: p : (4:14)
Set u=s y ksk krk r ky k kxk x , p=H(u)s ksk krk r=H(u)y ky k kxk x and U =H(p)H(u): (4:15) Then U s= ksk krk r, U y= ky k kxk x.
By Lemma 4.2, Problem 4.1 can be solved by determining r;x 2 R n and > 0,w~, ~ w i >0such that r T x krkkxk = s T y kskky k ; d( ~ w) ksk krk r= ky k kxk x (4:16)
or, equivalently, by solving the following:
Problem 4.3 Given a vectorwwith positive entries and two vectors s,y,s T y > 0, find r2R n and ~ w(i.e.",in ~ w="w+e) such that r T d(w)r~ krkkd( ~ w)rk = s T y kskky k =: p : (4:17)
The vectorsrand ~
wobtained in this way, = ky k ksk krk kd(w)rk~ , andx= d( ~ w )r,8 >0, solve (4.16).
Notice that condition (4.17) can be satisfied only if
p min s ~ w s max s ~ w s ;
thus, a choice ofw~ different from w~ =w(i.e. a pair(";)different from(1;0)) will be
necessary to make Problem 4.3 solvable for any0< 1.
Ifrhas only one nonzero entry, then Problem 4.3 has no solution for <1. Let us try
to solve Problem 4.3 with a vectorrof type
r=r i 1 e i 1 +r i n e i n (4:18) wherew i 1 =min s w s, w i n =max s w
s. The reason for this particular choice of the indeces
is linked to the criterion of making (4.17) solvable withw~ =wfor most values of , as it
will be clear later. Note that ifn=2, then (4.18) represents an arbitraryr.
So, we must determiner i1
;r
in
2Rand, eventually,(";)6=(1;0)such that ~ w i 1 r 2 i 1 +w~ in r 2 i n q r 2 i1 +r 2 in q ~ w 2 i1 r 2 i1 +w~ 2 in r 2 in = p or, equivalently, (1 )w~ 2 i1 r 4 i1 2r 2 i1 r 2 in ~ w i 1 ~ w i n + ~ w 2 i1 +w~ 2 in ! +(1 )w~ 2 in r 4 in =0: (4:17 0 )
We shall see below how to calculate the scalarsr i1,
r
in,
",, by considering separately
the cases = 1 and 0 < < 1. Once r i
1, r
i
n,
", have been computed, the vectors r=r i 1 e i 1 +r i n e i n, ~ w="w+e,x= (w~ i 1 r i 1 e i 1 +w~ i n r i n e i n
),8 >0, and the scalar
= ky k ksk s r 2 i 1 +r 2 i n ~ w 2 i1 r 2 i1 +w~ 2 in r 2 in ;
solve (4.16). As a consequence, the unitary matrix U = H(u)H(p), p;u defined in
Lemma 4.2, is such thatUd( w)U~
s=y, and so the Belle Epoque algorithm modified via
(4.110
) works.
Remark 1. By the particular form ofr, the above results hold unchanged if the vectors
~
wand"w+e, are defined, fors= i 1 ;i n, by ( ~ w ) s = w~ s, ("w+e) s = "w s +, and , fors6=i 1 ;i n, by ( w )~ s =w~ s, ("w+e) s =w s. Case =1. Equation (4.170 ) becomesr 2 i 1 r 2 i n (w~ i1 ~ w in ) 2 = 0. Then set w~ s = w s, s = 1;:::;nor (";)=(1;0)(we do not need to definew~ 6=w, in order to verify (4.17
0 )), and (r i1 ;r in )= (t;h)6=(0;0) w~ i1 =w~ in (t;0)or(0;t); t6=0 w~ i1 <w~ in : Case0< <1. Divide (4.170 ) by(1 )w~ 2 i1 r 4 in and find r 2 i 1 r 2 in : r 2 i 1 r 2 i n =a = 1 (1 )w~ 2 i 1 ~ w i 1 ~ w in + (w~ i 1 +w~ in ) 2 4 + (w~ i 1 ~ w in ) 2 4 r (w~ i1 ~ w in ) 2 h (wi~ 1 +wi~ n ) 2 4 ~ w i1 ~ w in i : (4:19)
Notice that botha +and a are positive. If 4wi 1 wi n (w i 1 +w in )
2 (this condition can be better
verified by our particular choice ofi 1, i n), set ~ w s =w s, s=1;:::;nor(";)=(1;0)(we
do not need to definew~ 6= w, in order to verify (4.17 0
)). Otherwise, in order to makea
real, chooseq >0such thatqw i1 1 q w inand 4qw i 1 1 q w i n (qw i1 + 1 q w in ) 2 ; and setw~ i 1 =qw i 1, ~ w i n = 1 q w i n, ~ w s = ( w s (two) q w i 1 (w i n w s ) wi n wi 1 + 1 q w i n (w s w i 1 ) wi n wi 1 (all) ; s6=i 1 ;i n
(see Remark 1) or, equivalently,w~ ="w+ewhere"= w i n q 2 w i 1 q(w in w i 1 ) ,= (q 2 1)w i 1 w i n q(w in w i 1 ) . Now 4w~ i 1 ~ w in =((w~ i 1 + w~ in ) 2 ) < 1. Thus (r i 1 ;r in ) = (jtj p a + ;t) and (r i ;r i )=(jtj p
a ;t)are defined inR and solve (4.17 0
