## NA Digest Sunday, March 24, 1991 Volume 91 : Issue 12

Today's Editor: Cleve Moler

Today's Topics:

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

From: Gene Golub <golub@Cholesky.Stanford.EDU>
Date: Mon, 18 Mar 91 14:07:44 PST
Subject: A Wonderful Report

Charlie Van Loan has written a wonderful report on recent developments
in matrix computations; it is entitled , "A Survey of Matrix
Computations." The report would make an excellent basis for a course
or seminar. If you are interested in receiving a copy, send a msg to
Charlie (na.vanloan@na-net) and ask for a copy. I'm sure you'll find
it of interest.

Gene

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

From: Joe Grcar <sepp@snll-arpagw.llnl.gov>
Date: Thu, 21 Mar 91 16:54:31 PST
Subject: Applied Math Is ...

I recall reading an essay titled "applied math is bad math" by
Halmos or some such, but I don't remember where. Can anyone
supply a reference? Joe Grcar, na.grcar

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

From: George Miel <MIEL@csfvax.hrl.hac.com>
Date: Mon, 18 Mar 91 19:18 PST
Subject: Reciprocal Pythagorean Sums

Reciprocal Pythagorean sums,
1/sqrt(a*a + b*b) (*)
are needed in certain applications, eg for computing Givens rotations in linear
algebraic methods. For Pythagorean sums, Moler and Morrison have presented
an algorithm that is simple, robust, and portable. Specifically, the
algorithm is attractive because it avoids range-reduction and overflow default
handling. However, the approximation of (*) based on m iterations of the
Moler-Morrison algorithm followed by reciprocation requires a total of 2m+1
divisions. For throughput intensive processors with no hardware division,
this approach is too slow. I was therefore led to the
PROBLEM: Find a division-free algorithm for reciprocal Pythagorean sums
with similar properties to the Moler-Morrison procedure, namely, with fast
convergence and no range-reduction nor overflow/underflow for a "large" set of
pairs a,b of machine numbers (say IEEE standard 754 floating point).
I have tinkered with this deceptively simple problem and so far the best I have
for single precision accuracy is an approximation for 1/sqrt(c) using a 3rd
degree polynomial approximation for the seed followed by one iteration of
Olver's method on f(x)=1/x**2-c, at a cost of 9 mult-adds. However, this
approach (as well as the usual division-free Newton-Raphson method for 1/sqrt)
requires setting c=a*a + b*b followed by range reducing c to a small interval.
Does anyone know of better alternatives?

George Miel, Hughes Research Laboratories, 3011 Malibu Cyn Rd, Malibu CA 90265
213-317-5841 miel@csfvax.hac.com

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

From: Bill White <bwhite@ucbvax.Berkeley.EDU>
Date: 15 Mar 91 17:02:00 GMT
Subject: Query About Floating Point Models

As part of the Ada 9X effort we considering changes to the definition
of Ada floating point number representation. We are looking at two
different models: the Brown model [1] and the LCAS model [2]. We are
informally soliciting comments on the following topics.

1.) Is there any other floating point model which is likely
to be a useful candidate for the Ada 9X standard?
2.) Which of floating-point models deal best with the very
important issues of portability and robustness? In
particular, I am concerned here with the essential
difference between the non-determinism of the Brown
model and the determinism of the LCAS model.

We are inclined to favor the Brown model, in the interests of
portability. As even numerics tyros (like me) know, a major problem
with numeric computations is the whimsical nature of optimization
algorithms. It is especially problematic to tell when operands will be in
extended precision registers and when they will be dumped to memory.
The attractive aspect of the Brown model is that the non-determinism
explicitly hides the optimization effects. The more highly detemined
LCAS model requires that the numerical analyst know the optimizer's
algorithm completely. This is not always possible, or even desirable,
as the algorithms may change and improve with different compiler releases.

The particular things I am interested in are:

1.) Pointers to any other reasonable floating point models.
Since we are working in an Ada framework, the models must
be general enough to analyze IEEE floating point, but not
be restricted to a single architecture.
2.) References in the literature to analyses of numerical algorithms
which use the floating-point model explicitly. The only
one I know of is the one in Brown's original paper. I
am certain there are more, but as I am not a numerical
analyst by training I am not sure how or where to proceed.

Any help would be appreciated.

Peace,
Bill White
[1] W.S. Brown, A Simple but Realistic Model of Floating Point
Computations, ACM Transactions on Mathematical Software, vol 7,
(1981) pp. 445-480.
[2] Mary Payne, Craig Schaffert, and Brian Wichmann, Proposal for a
Language Compatible Arithmetic Standard, appeared in SIGPLAN
Notices, vol 25, no 1., January 1991, pp. 59-86.

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

From: Alan Edelman <edelman@math.berkeley.edu>
Date: Sat, 23 Mar 91 23:27:24 PST
Subject: First Annual Large Dense Linear System Survey

THE FIRST ANNUAL LARGE DENSE LINEAR SYSTEM SURVEY

Without realizing it, about a year ago, I initiated the 0th annual large
dense linear system survey here in NANET. I've had so many requests
for a repeat survey that I decided to formalize the process by making it a
yearly event. (My calendar file should remind me to repeat this next year.)
I understand the NANET list has grown considerably since last time, so this
survey should reach many more people.
By default, none of the information you supply will be anonymous, however
I will keep any information strictly confidential upon request.
All of these questions relate to large DENSE linear systems.
Feel free to interject any comments between the lines, etc.
Results will be tallied into a LaTeX paper and will be available by
anonymous FTP from math.berkeley.edu.

Name __________________
_______________
_______________
_______________
Type of Institution ___ University ___ Independent Research Lab
___ Aircraft industry ___ Supercomputer Manufacturer
___ Other

Largest matrix size that you solved n=_________
Length of time ___________ (seconds, hours, weeks, ...)
on which machine ________________

Matrix was generated from ___ Moment Methods
___ Panel Methods for Lifting Potential Flow
___ Panel Methods for Potential Flow
___ Randomly (specify the distribution)
___ Other

Solution method used was ____ LU factorization
____ An iterative Method (Please specify___________)
(If an iterative method was used, did you take advantage of
symmetry, diagonal dominance, or any property at all?)

The solver was ___ your own
___ from a package (Please specify___________________)

The accuracy of the solution obtained
____ was clearly good (Specify how you know ____________________)
____ seems okay, but you are not really sure
____ is unknown

Any other comments, suggested questions for next year, etc?

I'm aware that aircraft manufacturers and supercomputing companies would be
most interested in these results, but might be reluctant to reveal their own
secrets. I would like to urge such manufacturers to feel free to mail me
anonymous responses by surface mail even without return addresses and names.
I will guarantee anonymity in any case upon request. Everyone will so benefit.
All I ask is that responses be truthful.

I trust that the academics out there who are doing this will be more than
happy to be forthcoming.

edelman@math.berkeley.edu
Alan Edelman
Dept of Mathematics
University of California
Berkeley, CA 94720

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

From: Jeff Scroggs <scroggs@matjfs.ncsu.edu>
Date: Sat, 23 Mar 91 17:00:16 -0500
Subject: Request for Domain Decomposition Bibliography

Louise Perkins and Jeff Scroggs would like to request bibliographic
data on heterogeneous domain decomposition. We are interested
in papers that deal with domain decomposition techniques for the
numerical solution of PDEs in which different modeling equations are
used in different subdomains.

This data will be collected into a publicly available report (issued
by ICASE, NASA Langley Research Center).

In order that this database be manageable, we have the following request:

Format: Bibliographic data should be in bibtex format. A set of
keywords is requested as part of the format.

Medium: Email messages to Louise Perkins or Jeff Scroggs.

Date: References for the first version should be in by April 5.

Assistance: To assist with placing the data in bibtex
format, send a request to either of us for the C
program BIBINPUT. This program will interactively
prompt you for the data, and produce a file with the
formatted entries.

Disclaimer: We are trying to keep this bibliography focused, hence
submissions that do not obviously deal with heterogeneous
domain decomposition will be eliminated.

Louise Perkins
54-1420
MIT
Cambridge, MA 02139
(617)253-1291
perkins@pimms.mit.edu

Jeffrey S. Scroggs
Box 8205
Mathematics Department
North Carolina State University
(919)737-7817
scroggs@matjfs.ncsu.edu

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

From: Renato Spigler <SPIGLER%IPDUNIV@ICNUCEVM.CNUCE.CNR.IT>
Date: Tue, 19 Mar 91 14:17:19 SET
Subject: Venice Summer School on Applied Mathematics

Between June 17 and 28, 1991, a Summer School will be held in Venice, Italy,
downtown, at the Ateneo Veneto (Campo S.Fantin 1897,S.Marco,30124 Venice).
Speakers and topics will be

1) G.H.GOLUB, Stanford, "Matrices,moments,and orthogonal polynomials",
2) E.HAMEIRI, Courant Institute, NYU, "Localized instabilities in MHD plasmas
and in classical fluids",
3) P.A.MARKOWICH, TU-Berlin and Purdue, "Mathematical modelling of
semiconductors",
4) G.MILTON, Courant Institute, NYU, "Exploring the properties of composite
materials".

The Scientific Committee includes V.Boffi, F.Brezzi, G.Frosali, and D.Trigiante.
Attendence will be limited to 50 participants. Send applications to Renato
SPIGLER, Dipartimento di Metodi Mod. Mat. Sci. Appl., Universita' di Padova,
Via Belzoni, 7-35131 Padova (Italy), phone 0039-49-83 19 14, 83 19 01 ,
fax 0039-49-83 19 95, e-mail spigler at ipduniv.bitnet.

The event is sponsored/jointly organized/with the collaboration of
Gruppo Nazionale per la Fisica Matematica del CNR
UNESCO
Courant Institute of Mathematical Sciences, NYU
SIAM

Renato Spigler

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

From: Renato Spigler <SPIGLER%IPDUNIV@ICNUCEVM.CNUCE.CNR.IT>
Date: Tue, 19 Mar 91 14:52:44 SET
Subject: Workshop for Industry in Venice

On May 3, 1991, there will be a one-day workshop on Mathematics for Industry,
in Venice, Italy, at the Istituto Veneto di Scienze, Lettere e Arti
(Campo S.Stefano, S.Marco 2945). This event is promoted by ALPE ADRIA,
the J. Kepler University of Linz, S.A.S.I.A.M.-Tecnopolis, and the
University of Padova. It will also held under the auspices of the European
Consortium for mathematics in the Industry (ECMI), and the Consorzio
Venezia-Ricerche.

Four mathematicians from the Academia and two or three from the industrial
worldwill present a few case studies, as examples of successful collaboration
between the two environments. A free, informal discussion willbe organized in
the afternoon, and, possibly, some new, open problems will be introduced for
the purpose of establishing new collaborations.

The event is aimed mainly to the Alpe Adria community.

Renato Spigler
(phone 0039-49-831914, 831901, fax 831995, e-mail spigler at ipduniv.bitnet)

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

From: Ed F. Deprettere <ed@dutentb.ET.TUDelft.NL>
Date: Tue, 19 Mar 91 17:51:00 +0100
Subject: Positions at Delft University of Tehcnology

Faculty and PH.D candidate positions available, Network Theory Section
(Microelectronics Group), Department of Electrical Engineering,
Delft University of Technology, Delft The Netherlands.

Junior Scientist Position
and
Ph.D. Candidate Position

In connection with the project Modeling and Determination of
Parasitics in Submicron VLSI Layouts at the Network Theory
Section of the Faculty of Electrical Engineering at Delft
University of Technology, Delft, The Netherlands, the above
mentioned positions are currently open.

The project aims at an advanced system for the modeling of
submicron IC interconnect structures. The ongoing
miniaturization of IC's-0.5 micron feature size is quickly
becoming available-causes new design related problems.
Because of their minute dimensions, the circuit elements
behave differently. One aspect of this changed behavior is
the relative increase of parasitic resistances, ground
capacitances and coupling capacitances. An IC designer who
does not properly account for these effects runs the risk
that his design does not function as intended. The problem
is especially severe in combined analog/digital (e.g.
BICMOS) circuits.

Not only are these parasitic effects becoming more
prominent, they are also becoming more difficult to
Instead, completely new methods are necessary to capture
these effects into suitable models. The goal of the present
case project is to develop these methods and models.

You will be part of a team carrying out research to develop
such a modeling system. You will build on the knowledge
available in the laboratory, as was developed in a precursor
project. After a thorough study of those results, you will
extend the theory in order to come to a system capable of
delivering accurate (but not over-accurate) models that
enable designers to predict the crosstalk between different
subcircuits. Relevant physical aspects are e.g.:

+ interconnect capacitances of non-planar structures,
+ capacitive effects of diffused conductors,
+ the resistive nature of the substrate.

The newly developed theory will lead towards a prototype
implementation in the Nelsis IC design system.

REQUIREMENTS

The positions can be characterized as multi-disciplinary:
electrical engineering, physics, linear algebra, numerical
mathematics and computer science are all relevant.
Applicants should have a grade in one of these disciplines,
preferably their education and/or experience shows a good
mix of these disciplines. It is the intention that the

NOTE

An appointment will be temporal with a duration of 4 years.

INFORMATION

Dr. N.P. van der Meijs
tel. +31-15-786258
email: nick@et.tudelft.nl
or
Prof. P. Dewilde
tel. +31-15-786234,
email: dewilde@dutentb.et.tudelft.nl.

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

From: Mike Osborne <mike@thrain.anu.edu.au.
Date: Wed, 20 Mar 91 07:37:32 +1000
Subject: Positions at Australian National University

The Australian National University
Centre for Information Science Research
ANU Supercomputer Facility

Research Positions

The ANU and Fujitsu Japan have established a large number of research
and development projects in advanced computing and its applications
under the general direction of the Centre for Information Science
Research at the University. This Centre, established as part of a
strategic plan by the University to create a centre of international
standing, acts as a focus of advanced computing throughout the
University and brings together diverse groups in the Institute of
research and teaching.

The ANU has assembled one of the most powerful and broadly-based
computing resources at the ANU include a Fujitsu VP2000 vector
processor, a Connection Machine with 16K processors and a 128
processor Fujitsu AP1000. Each machine is capable of peak speeds of
over 1 Gigaflops.

Two positions are now available in a new project to develop
state-of-the-art mathematical software for a parallel vector
processing environment. Mathematicians with experience in algorithm
and software development are sought to join this project which is
under the direction of staff from the School of Mathematical Sciences
and the Computer Science Laboratory, Research School of Physical
Sciences and Engineering. Appointees will be expected to interact
closely with these groups which are also engaged in the development of
algorithms and software for the experimental multi-processor AP1000
supercomputer.

These positions are centred on algorithm and software development for
the parallel models of the VP2000 series of vector processors.
Appointees will be required to work on software development for
multi-processor VP2000 series machine will be made available.

Applicants should have a firm background in computational mathematics
and a higher degree in a scientific or mathematical discipline with
considerable research experience. Less experienced and qualified
candidates may also be considered. We are particularly seeking
computational mathematicians with an interest in eigenvalue problems
and FFTs. Experience or a deep understanding of parallel or vector
processing or experience in software development would be very
advantageous. The ability to complete projects on schedule is
essential.

The duration of the appointment will be initially for one year, but it
is hoped that funding will become available over a longer period.

Persons wishing to take the posts on secondment from other positions
are encouraged to apply. Appropriate financial arrangements will be
made with the appointee's home institution in this case.

the range of Post-doctoral Fellow (\$28792-\$32762) through to Senior
Research Fellow (\$45729-\$54255). The level of appointment will
reflect the candidate's experience.

Further information is available from, Dr R Gingold, Phone: (06) 249
3437 or 249 4519. Fax: 247 3425. E-mail: rag900@anusf.anu.edu.au.or
Professor R Brent (249 3329) or Professor M Osborne (249 4501).

Applications including curriculum vitae, list of publications and the
names and addresses (including Fax) of three referees should be
submitted in duplicate to The Registrar, The Australian National
University, GPO Box 4, Canberra ACT Australia 2601 by the closing date
April 15. Post no. CISR 13.3.1
The University reserves the right not to make an appointment
or to appoint by invitation at any time. The ANU is an equal
opportunity employer.

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

From: Karl-Heinz Brakhage <EZ010BR%DACTH11.BITNET>
Date: Wed, 20 Mar 91 17:50:10 MEZ
Subject: Professur C4 fuer Mathematik in Aachen

RHEINISCH-WESTFAELISCHE TECHNISCHE HOCHSCHULE AACHEN

In der Mathematisch-Naturwissenschaftlichen Fakultaet ist am Institut
fuer Geometrie und Praktische Mathematik eine

P R O F E S S U R C 4 F U E R M A T H E M A T I K
(Fiebiger-Programm)

zu besetzen.

Erwartet wird die Vetretung des Faches Mathematik in Forschung und
Lehre und die Mitwirkung an der Ausbildung von Studierenden der
Mathematik, Ingenieur- und Naturwissenschaften. Zu den Aufgaben des
Institutes gehoert das Vorlesungsangebot in Numerik sowie
Darstellender Geometrie.

Erwuenscht ist ein Forschungsgebiet aus der Numerischen Analysis, das
Bezug zu Ingenieur- und Naturwissenschaften hat, z.B. Numerische
Mathematik der Differentialgleichungen oder/und numerisch-geometrische
Verfahren fuer hoeher dimensionale Probleme.

Einstellungsvoraussetzung sind Habilitation oder gleichwertige
wissenschaftliche Leistungen sowie paedagogische Eignung.

Die Bewerbung von Schwerbehinderten ist erwuenscht.

Bewerberinnen und Bewerber werden gebeten, sich mit den ueblichen
Unterlagen (Lebenslauf, Darstellung des wissenschaftlichen bzw.
beruflichen Werdegangs, Schriftenverzeichnis) bis zum

15. Mai 1991

an den

Dekan der Mathematisch-Naturwissenschaftlichen
Fakultaet der RWTH Aachen
Templergraben 64
D-5100 Aachen.

Auch Hinweise auf geeignete Persoenlichkeiten sind erwuenscht.

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

From: Richard Brualdi <brualdi@math.wisc.edu>
Date: Wed, 20 Mar 91 10:25:48 cst
Subject: Contents, Linear Algebra and Its Applications

Proceedings of the First Conference of the International
Linear Algebra Society

Special Editors: Wayne Barrett, Daniel Hershkowitz,
and Donald Robinson

George W. Soules (Princeton, New Jersey)
The Rate of Convergence of Sinkhorn Balancing 3

Marvin Marcus (Santa Barbara, California)
Multilinear Methods in Linear Algebra 41

Russell Merris (Hayward, California)
Almost All Trees Are Co-immanantal 61

Daniel J. Scully (Saint Cloud, Minnesota)
Maximal Rank-One Spaces of Matrices Over Chain Semirings. I. u-Spaces 67

Ronald J. Stern (Montreal, Quebec, Canada) and
Invariant Ellipsoidal Cones 81

Bob Grone and Steve Pierce (San Diego, California)
Extremal Positive Semidefinite Doubly Stochastic Matrices 107

Shmuel Friedland (Chicago, Illinois)
Pairs of Matrices Which Do Not Admit A Complementary Triangular Form 119

Jerome Dancis (College, Park, Maryland)
Invertible Completions of Band Matrices 125

R. Loewy, D. R. Shier, and C. R. Johnson
(Williamsburg, Virginia)
Perron Eigenvectors and the Symmetric Transportation
Polytope 139

I. Gohberg (Ramat Aviv, Israel), M. A. Kaashoek
(Amsterdam, The Netherlands), and H. J. Woerdeman
(La Jolla, California)
A Note on Extensions of Band Matrices With Maximal and
Submaximal Invertible Blocks 157

Robert Grone (San Diego, California)
On the Geometry and Laplacian of a Graph 167

Chi-Kwong Li (Williamsburg, Virginia) and Nam-Kiu Tsing
(College Park, Maryland)

Michael E. Lundquist (Provo, Utah) and
Charles R. Johnson (Williamsburg, Virginia)
Linearly Constrained Positive Definite Completions 195

Rafael Bru (Valencia, Spain), Leiba Rodman
(Williamsburg, Virginia), and Hans Schneider
Extensions of Jordan Bases for Invariant Subspaces of a Matrix 209

R. A. Brualdi (Madison, Wisconsin) and
Small Matrices of Large Dimension 227

Yik-Hoi Au-Yeung and Che-Man Cheng (Hong Kong)
Permutation Matrices Whose Convex Combinations
Are Orthostochastic 243

Jeffrey L. Stuart (Hattiesburg, Mississippi) and
James R. Weaver (Pensacola, Florida)
Matrices That Commute With a Permutation Matrix 255

Jean H. Bevis and Frank J. Hall (Atlanta, Georgia)
Integer LU-Factorizations 267

Pal Rozsa (Budapest, Hungary), Roberto Bevilacqua,
Francesco Romani, and Paola Favati (Pisa, Italy)
On Band Matrices and Their Inverses 287

Charles R. Johnson (Williamsburg, Virginia) and
Erik A. Schreiner (Kalamazoo, Michigan)
Explicit Jordan Form for Certain Block Triangular Matrices 297

Jorma Kaarlo Merikoski (Tampere, Finland)
On c-Norms and c-Antinorms on Cones 315

R. B. Bapat (New Delhi, India)
An Interlacing Theorem for Tridiagonal Matrices 331

Olga Taussky and John Todd (Pasadena, California)
Another Look at a Matrix of Mark Kac 341

M. C. Gouveia (Coimbra, Portugal) and R. Puystjens
(Gent, Belgie@a2)
About the Group Inverse and Moore-Penrose Inverse of a Product 361

Hans Joachim Werner (Bonn, Germany)
Some Further Results on Matrix Monotonicity 371

Yair Censor (Haifa, Israel) and Stavros A. Zenios
Interval-Constrained Matrix Balancing 393

Shmuel Friedland (Chicago, Illinois)
Quadratic Forms and the Graph Isomorphism Problem 423

H. Bart (Rotterdam, The Netherlands) and H. K. Wimmer
(Wurzburg, Germany)
Simultaneous Reduction to Triangular and Companion Forms
of Pairs of Matrices: The Case rank(I_AZ)=1 443

Wayne Barrett, Donald Robinson (Provo, Utah),
and Daniel Hershkowitz (Haifa, Israel)
REPORT: Inaugural Conference of the International Linear Algebra Society, 12-15 August 1989, Brigham Young University, Provo, Utah, USA 463

Special Issues in Progress

1. Interior Point Methods for Linear Programming; special editors are D. Gay, M.
Kojima, and R. Tapia. To appear as Volume 152, July 1, 1991.

2. Iterations in Linear Algebra and Its Applications (Dedicated to G. H. Golub,
R. S. Varga, and D. M. Young); special editors are O. Axelsson, J. de Pillis,
M. Neumann, W. Niethammer, and R. J. Plemmons. To appear as Volumes 154/155,
August/September 199

3. Algebraic Linear Algebra; special editors are Robert M. Guralnick, William H.
Gustafson, and Lawrence S. Levy. To appear as Volume 157, October 15, 1991.

4. Proceedings of the Auburn 1990 Matrix Theory Conference; special editors are
David Carlson and Frank Uhlig. Submission deadline: August 1, 1990. Details
provided with the conference announcement.

5. Proceedings of the Sixth Haifa Conference on Matrix Theory; special editors
are A. Berman, M. Goldberg, and D. Hershkowitz. Submission deadline: October 1,
1990. Details provided with the conference announcement.

6. Proceedings of the International Workshop on Linear Models, Experimental
Designs and Related Matrix Theory, (August 6-8, 1990, Tampere, Finland);
special editors are Jerzy K. Baksalary and George Styan. Submission deadline:
October 31, 1990. Details provided with the conference announcement.

7. Proceedings of the Second NIU Conference on Linear Algebra, Numerical Linear
Algebra and Applications, (May 3-5, 1991, Northern Illinois University, DeKalb,
Illinois); special editors are Biswa Dutta and Robert Plemmons. Submission
deadline: July 31, 1991. Details provided with the conference announcement.

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

End of NA Digest

**************************
-------