Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!krj Newsgroups: ut.na From: krj@na.toronto.edu (ANT Privileged User) Subject: NA Digest Volume 89 : Issue 50 Message-ID: <90Jan2.170511est.1krj@neat.cs.toronto.edu> Organization: Department of Computer Science, University of Toronto Distribution: ut Date: 2 Jan 90 22:06:08 GMT Lines: 220 NA Digest Sunday, December 24, 1989 Volume 89 : Issue 50 Today's Editor: Cleve Moler Today's Topics: Nonsymmetric QR in LAPACK LINC Netlib in Europe Season's Greetings from SIAM .. and from Jerzy Wasniewski .. and from NA Net News ------------------------------------------------------- From: Jim Demmel 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 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 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 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 Date: Wed, 20 Dec 89 22:18:28 EST 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 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 ************************** ------- Reposted by Prof. Kenneth R. Jackson, krj@na.toronto.edu (on Internet, CSNet, Computer Science Dept., ARPAnet, BITNET) University of Toronto, krj@na.utoronto.ca (on CDNnet and other Toronto, Ontario, X.400 nets (Europe)) Canada M5S 1A4 ...!{uunet,pyramid,watmath,ubc-cs}!utai!krj (Phone: 416-978-7075) (on UUCP) (FAX: 416-978-4765)