**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 <demmel@robalo.nyu.edu>

Date: Mon, 18 Dec 89 12:49:26 EST

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

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

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

******************************************************************************

* *

* \ | / *

* \ | / *

* \ | / 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

*

+ +

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

Best Wishes for the Holidays.

== Gene, Cleve, Mark

------------------------------

End of NA Digest

**************************

-------