NA Digest Sunday, December 24, 1989 Volume 89 : Issue 50
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Jim Demmel <demmel@robalo.nyu.edu>
Date: Mon, 18 Dec 89 12:49:26 EST
Subject: Nonsymmetric QR in LAPACK
This is in response to Warren Ferguson's and Cleve Moler's comments on
nonsymmetric QR in the last NA Digest. I will outline our approach here;
for details see
"LAPACK Working Note 8: On a Block Implementation of Hessenberg
Multishift QR Iteration", Z. Bai and J. Demmel, ANL/MCS-TM-127,
Mathematics and Computer Science Division, Argonne National Laboratory
Argonne, IL, January 1989
or
"On a Block Implementation of Hessenberg Multishift QR Iteration",
Z. Bai and J. Demmel, International Journal of High Speed Computing,
v. 1, n. 1, pp. 97-121, 1989
Briefly, instead of using a double shift and chasing a 2 by 2 bulge, we
use a k by k shift and chase a k by k bulge. The shifts are taken as
the eigenvalues of the trailing k by k submatrix (which we compute using
HQR). If we chased the bulge one column at a time, that would be a BLAS Level 2
operation (applying a Householder transformation). Instead, we chase the
bulge p columns at a time, which lets us use more efficient BLAS Level 3
operations but at the cost of more flops. There are also a number of ways
to use Level 3 BLAS, which may have different performances on different
machines. We have chosen one of these for our beta release. Finally, if the
matrix is sufficiently small (less than maxb), we just use HQR.
So there are three parameters (k, p and maxb) which need to be tuned for each
architecture. Our next beta release will test various values of k, p and
maxb to help us do this tuning.
The stopping criterion remains unchanged within HQR when we call it. Outside
HQR, we only check for single small subdiagonals instead small pairs
of subdiagonals. We do this because of the difficulty of starting a
k by k shift in the middle of the matrix with a small pair of adjacent
subdiagonals. A variation we could add would be to do a 2 by 2 bulge chase in
case we found a small pair.
As you can see, there are quite a few variations to explore. We do not expect
to be able to find the optimal parameters for all machines and all dimensions
by the time the package is publically released, so future improvements are
to be expected.
I also wish to mention some interesting work on the HQR shift strategy by
Steve Batterson at Emory (sb@mathcs.emory.edu). He has found a normal 3 by 3
Hessenberg matrix which is essentially a fixed point (or in a limit cycle)
for HQR, including the ad hoc shift. In fact, it is a fixed point for any
sequence of Wilkinson and ad hoc shifts in any order. It is an unstable
fixed point, so eventually roundoff will cause the matrix to drift away
from the fixed point and converge; this did take 40 steps in his example,
however.
Jim Demmel
------------------------------
From: Annie Cuyt <cuyt@ccu.uia.ac.be>
Date: Fri, 22 Dec 89 11:22:52 GMT
Subject: LINC
Can anyone indicate a reference on the fourth generation language LINC
(on UNISYS)? Replies can be sent through the na-net at na.cuyt.
Thanks a lot in advance!
------------------------------
From: Petter Bjorstad <petter@eik.II.UIB.NO>
Date: Fri, 22 Dec 89 16:57:22 +0100
Subject: Netlib in Europe
In the interest of reducing the load on trans-atlantic satellite
links, a netlib service has been running for some time in Oslo.
Pick an address from the following list appropriate to your system.
Internet: netlib@nac.no
EARN/BITNET: netlib%nac.no@norunix.bitnet
X.400: s=netlib; o=nac; c=no;
EUNET/uucp: nac!netlib
The machine nac.no has 64Kb/s Internet connections, is a gateway
for X.400, and is the backbone machine in Norway for uucp mail.
Contact petter@eik.ii.uib.no for questions about connecting to nac.no;
continue to send comments and contributions for the netlib collection
to ehg@research.att.com.
Because of high-speed network connections and historically close
working relationships, it has been possible to keep netlib@nac.no and
netlib@research.att.com exactly in sync. Reliable distribution and
prompt installation of updates tends to be an operational nightmare
otherwise, so we discourage the proliferation of duplicate netlibs
unless there is clear value added.
Seasons Greetings,
Petter Bjorstad
Eric Grosse
------------------------------
From: SIAM <SIAM@wharton.upenn.edu>
Date: Tue, 19 Dec 89 08:53 EDT
Subject: Season's Greetings from SIAM
******************************************************************************
* *
* \ | / *
* \ | / *
* \ | / SEASON'S GREETINGS *
* *
* x FROM EVERYONE *
* x *
* xxx AT SIAM *
* xxx *
* x TO ALL OF YOU *
* xxxxxxx *
* xxxxxxx AND *
* xxxxxxx *
* xxxxxxx BEST WISHES *
* xxxxxxx *
* xxxxxxx FOR A *
* xxxxxxx *
* xxxxxxx HAPPY AND HEALTHY *
* xxxxxxx *
* xxxxxxx NEW YEAR! *
* xxxxxxx xx *
* xxxxxxxxxxxxxxxxxxxx xx *
* xxxxxxxxxxxxxxxxxxxxxx xx *
* xxxxxxxxxxxxxxxxxxxx xx *
* *
* *
******************************************************************************
------------------------------
From: Jerzy Wasniewski <mfci!wasniews@uunet.UU.NET>
Date: Wed, 20 Dec 89 22:18:28 EST
Subject: .. and from Jerzy Wasniewski
Subject: .. and from Jerzy Wasniewski
*
+ +
A Merry Christmas and +O+ =============
+ + | . | . |
a Happy New Year +* O+ | . | . |
+ O + | . | . |
1 9 9 0 + @ + | . | . |
+ @ * + |----+----|
+ @ O + | .| .. |
+ * O + | . | . |
+ 0X O #+ | . | . |
+ O *#* + =============
+O 0 * @ +
+ % * +
+O * * 0 & +
---------------
------ | | -------
|#-#-| ------- |#-#-#|
------ -------
Best regards,
Jerzy
------------------------------
From: Cleve Moler <moler@mathworks.com>
Date: Sat Dec 23 16:48:36 PST 1989
Subject: .. and from NA Net News
Best Wishes for the Holidays.
== Gene, Cleve, Mark
------------------------------
End of NA Digest
**************************
-------