NA Digest Sunday, March 19, 2000 Volume 00 : Issue 12

Today's Editor:
Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to

URL for the World Wide Web:

From: Francois Robert <>
Date: Sun, 12 Mar 2000 21:04:56 +0100
Subject: A Query About Matrices and Eigenvalues

Let M be a nonsingular n by n matrix. Set A = M'*M , and take for simplicity
the columns of M of Euclidean norm 1. Then diag(A) = I.
It is easy to prove that:

* the eigenvalues of A belong to the open interval (0, n)
* Moreover, if A is tridiagonal, then its eigenvalues belong to (0,2)
(a little bit harder, since a crude localization gives (0,3) )

Question: Is it possible to derive similar localizations when A is
pentadiagonal, heptadiagonal, and so on? One should get (0, n) for a full A .

Thanks a lot for any help!


From: Amelia Garcia <>
Date: Fri, 17 Mar 2000 09:51:26 +0100
Subject: Stability in Runge-Kutta-Nystrom

I am writing to ask for information on absolute stability in
Runge-Kutta-Nystrom methods. I should be very greatful if someone sends
me references about this.

Amelia Garcia
Dpto. de Matematica Aplicada a la Ingenieria
E.T.S. de Ingenieros Industriales
Universidad de Valladolid
Paseo del Cauce s/n
47011-Valladolid, Spain


From: Aloke Phatak <Aloke.Phatak@cmis.CSIRO.AU>
Date: Sun, 19 Mar 2000 13:14:18 +0800
Subject: Results on Conjugate Gradient Method

There are lots of results scattered throught the literature on the
Conjugate Gradient method, but I've yet to come across any results on the
Euclidean norms of the iterates themselves. In particular, is there an
explicit proof of the result that when solving Ax = b with A (n x n)
symmetric positive definite and initial estimate x(0) = 0,

||x(1)|| < ||x(2)|| < ... < ||x(n)|| ?

Any pointers to the literature would be much appreciated.

My interest stems from the fact that for x(0) = 0, CG is identical to a
widely used estimator of the parameters in linear regression know as
the "partial least squares" estimator. In statistical parlance, it is
a shrinkage estimator, but existing proofs of its shrinkage properties
are somewhat cumbersome.

Aloke Phatak
CSIRO Mathematical and Information Sciences .


From: Ken Turkowski <>
Date: Wed, 8 Mar 2000 01:40:44 -0800
Subject: Transformation of a Hessian or Covariance Matrix

I'm transforming one image via a projective transformation to another,
attempting to find the best parameters for the projective transformation
by means of least squares optimization (Levenberg-Marquardt). In order to
increase the stability of the optimization (i.e. to make the error
landscape "rounder" instead of oblong), I convert the coordinate system
so that the origin is at the center of the images, and I scale the images
so that the pixel coordinates go from -1 to +1 (instead of
[0,767]x[0,512]). A multi-resolution pyramid is used for the
registration, so there is a coordinate change between the levels of the
pyramid as well.

M* = arg min \ e(p)^2
M /_
p in omega

e(p) = I0(p) - W(I1; p, M)

M is a vector of parameters for the projective transformation
p is the coordinates of a pixel
omega is the overlap region between the first image and the
transformed second one
I0() and I1() are two images
W() is an image warping function

The Taylor series expansion at M is given by

E(M + a) = E(M) + G . a + _ a^t . H . a + ...


d E
G = ___ is the gradient of E with respect to the warp parameters M
d M

d^2 E
H = _________ is the Hessian
d Mi d Mj

At the optimum, the gradient is essentially zero (ignoring inevitable
noise), and the error is some finite number, and error landscape in the
neighborhood of the optimum is described by the Hessian:

E(M* + a) =~ E(M*) + _ a^t H a

The Hessian is either supplied or computed in many optimization schemes
(e.g. supplied in Levenberg-Marquardt, computed in BFGS, but not used at
all in conjugate gradient).

The transformation of the projective transformation from the stabilized
coordinate system to the standard upper-left integral image coordinate
system is given by:

| Sl 0 Cxl | | Sr 0 Cxr | -1
M' = | Sl Cyl | . M . | 0 Sr Cyr |
| 0 0 1 | | 0 0 1 |

where the S's are scale factors, and the C's are offsets, and the
projective transformation M is represented in matrix form

| m00 m01 m02 |
M = | m10 m11 m12 |
| m20 m21 1 |

such that

m00 * x + m01 * y + m02
x' = _______________________
m20 * x + m21 * y + 1

m10 * x + m11 * y + m12
y' = _______________________
m20 * x + m21 * y + 1

performs the perspective transformation.

The question is how to transform the Hessian?

Perhaps the real question is:

What is the appropriate chain rule for second derivatives for scalar
functions of vector variables?

Or, more to the point,

Given the Taylor expansion of a function of several variables

E(m + a) = E(m) + G(m) . a + a^t . H(m) . a

and a transformation of parameters

m = t(n)

what is the Taylor expansion

E(t(n + b))

Ken Turkowski
Immersive Imaging Technologist
Apple Computer, Inc.


From: Paul Barton <pib@MIT.EDU>
Date: Mon, 13 Mar 2000 14:56:30 -0500
Subject: DAEPACK Version 1.0 Announcement


The Massachusetts Institute of Technology is pleased to announce the
availability of DAEPACK version 1.0 for academic and commercial uses

DAEPACK is a symbolic and numeric library for general numerical
calculations. What distinguishes DAEPACK from other software libraries for
numerical computations is a set of symbolic components that operate
directly on very general Fortran-90 code provided by the user. The
symbolic components take as input a set of Fortran-90 source files defining
a system of equations of interest and generate a new set of Fortran-90
subroutines and functions computing quantities such as analytical
derivatives matrices, sparsity patterns, etc. The original Fortran-90 code
may contain an arbitrary number of subroutine and function calls, common
blocks, sophisticated solution strategies embedded within the model
evaluation, etc. The information generated automatically by DAEPACK is
exploited in a collection of state-of-the-art numerical algorithms for
performing tasks such as solution of large sets of nonlinear equations,
efficient numerical integration and parametric sensitivity calculation,
hybrid discrete/continuous simulation, and others. In addition, this new
information can be used with third party or custom numerical algorithms to
provide information that would otherwise have to be generated by hand.

Currently, the symbolic components generate:

1) General derivative matrices, J(x)S, where J(x) is the Jacobian matrix
and S is and arbitrary conformable matrix. Setting S equal to the
identity matrix yields the Jacobian matrix. Sparsity is exploited both in
derivative computation and storage.
2) Sparsity patterns.
3) Discontinuity-locked models.
4) Interval extensions of the original system of equations.

In all of the cases above, new code is generated that can be compiled and
linked into other applications to provide the desired information.

Currently, the numerical components provided with DAEPACK are:

1) Block solution of large sparse sets of nonlinear algebraic equations.
The structural information of the system of equations obtained with the
sparsity pattern code described above is used to permute the system into
block lower triangular form where the overall system of equations is
solved as a sequence of smaller blocks. Derivative code is generated in
order to extract efficiently the submatrix of the Jacobian corresponding to
the current block.
2) Efficient numerical integration and parametric sensitivity calculation
exploiting the sparsity pattern and analytical derivatives generated
3) Hybrid discrete/continuous numerical integration and parametric sensitivity
calculation using the sparsity pattern, analytical derivatives, and
discontinuity-locked model generated automatically.
4) Intelligent model analysis based on the Dulmage-Mendelsohn
decomposition, exploiting the sparsity pattern generated automatically.

DAEPACK is available on the following platforms: Windows 9x, Windows NT, UNIX
(HPUX and Sun Solaris), and Linux. The Windows versions of DAEPACK are
provided with a graphical user interface that facilitates the automatic
generation of code using the symbolic components.

Future releases of DAEPACK will include a larger set of symbolic and
numeric algorithms and a graphical environment for "numerical
flowsheeting", the construction of numerical algorithms graphically.
Furthermore, greater support for the automatic construction of CAPE-Open
compliant components from legacy Fortran code will be provided.

More information about DAEPACK can be found at the following website:

For additional information, including licensing, contact:

John Tolsma
Postdoctoral Associate
Department of Chemical Engineering
Massachusetts Institute of Technology
77 Massachusetts Avenue Room 66-365
Cambridge MA 02139
(phone) 617-253-5513
(fax) 617-258-5042

Paul I. Barton
Associate Professor
Department of Chemical Engineering
Massachusetts Institute of Technology, 66-464
77 Massachusetts Avenue
Cambridge MA 02139


From: Trini Flores <>
Date: Fri, 17 Mar 2000 09:10:20 -0500
Subject: SIAM Annual Meeting

2000 SIAM Annual Meeting
July 10-14, 2000
Westin Rio Mar Beach Resort and Country Club
Rio Grande, Puerto Rico


Your contributed abstracts are still welcome! To ensure inclusion in
the Final Program, please send your abstract to SIAM by APRIL 25,

Don't miss the boat...come, catch the sun!

Even if you don't want to send an abstract, plan to join your SIAM
colleagues for fun in Puerto Rico! Registration materials will be
posted on the web site by March 27.

Visit and submit now your 75-word abstract
in LaTeX format, by using the LaTeX macro available at and send it to on
or before APRIL 25, 2000.

See you in Puerto Rico!

SIAM Conferences
3600 UCSC
Philadelphia, PA 19104 USA
800-447-SIAM (US and Canada only)
fax 215-386-7999


From: Nick Trefethen <>
Date: Sat, 18 Mar 2000 16:47:32 GMT
Subject: Meeting on Pseudospectra of Random Nonhermitian Matrices


Friday, 30 June 2000
Oxford University Computing Laboratory


Prof. J. Chalker (Oxford)
Dr. M. Contedini (Oxford)
Prof. E. B. Davies, FRS (KCL)
Dr. M. Embree (Oxford)
Prof. I. Goldsheid (QMW)
Dr. B. A. Khoruzhenko (QMW)
Prof. G. Strang (MIT)
Prof. L. N. Trefethen (Oxford)

For information contact Shirley Day,


From: Yang Xiaoqi <>
Date: Mon, 13 Mar 2000 09:47:05 +0800
Subject: Sino-Japan Optimization Meeting

The First Sino-Japan Optimization Meeting
Hong Kong, October 26-28, 2000

The meeting aims to provide a forum for researchers, who are from Japan,
Mainland China, Hong Kong, Taiwan, Singapore, other countries and regions,
and working in the area of optimization, to gather together to report
and exchange their latest works on optimization.

Linear and Nonlinear Optimization
Continuous and Discrete Optimization
Deterministic and Stochastic Optimization
Smooth and Nonsmooth Optimization
Single- and Multi-Objective Optimization
Integer and Combinatorial Optimization
Convex and Nonconvex Optimization


The Sino-Japan Optimization Meeting (SJOM) is endorsed by the Mathematical
Programming Society (MPS), the Research Association of Mathematical
Programming (RAMP), Japan, and the Chinese Mathematical Programming Society.
The First Sino-Japan Optimization Meeting (SJOM 2000) is organized
by The City University of Hong Kong and The Hong Kong Polytechnic University.

Liqun Qi (The Hong Kong Polytechnic University), Co-Chair
Jianzhong Zhang (City University of Hong Kong), Co-Chair
Chuangyin Dang (City University of Hong Kong),
Xiaoqi Yang (The Hong Kong Polytechnic University), Treasurer


Rainer Burkard (Technische Universitat Graz, Austria)
Gianni Di Pillo (Universita di Roma ``La Sapienza'', Italy)
Carl Timothy Kelley (North Carolina State University, USA)
Jean-Philippe Vial (University of Geneva, Switzerland)


e-mail: Eva Yiu ( or Peggy Chan (
or contact Organization Committee Members


From: George Miminis <>
Date: Sun, 12 Mar 2000 18:26:43 +0200
Subject: Department Head Position at Memorial University


Applications and nominations are invited for the position of Head of the
Department of Computer Science. The starting date is negotiable.
Memorial University is the largest university in Atlantic Canada. As
the province=92s only university, Memorial plays an integral role in the
educational and cultural life of Newfoundland and Labrador. Offering
diverse undergraduate and graduate programs to almost 16,000 students,
Memorial provides a distinctive, and stimulating environment for
learning. St. John=92s is a very safe, friendly city with great historic
charm, a vibrant cultural life, and easy access to a wide range of
outdoor activities. The Department of Computer Science has 20 faculty
and 13 technical and support staff, offers a full range of undergraduate
and graduate programmes and is a critical component of an
interdisciplinary computational sciences (graduate) programme.

The ideal candidate for head will have a strong record of research and
teaching in computer science or related area, demonstrated
administrative skills, a commitment to collegial
governance, interests that span all aspects of information technology
and a desire to create links with industry and other academic units on
campus. Applications or nominations, which include a Curriculum Vitae
and the names of at least three potential referees should be sent to Dr.

Edgar G. Goodaire, Chair, Search Committee for Head of Computer
Science, Office of the Dean of Science, Memorial University of
Newfoundland, St. John's, Newfoundland, Canada, A1B 3X7. Applications
received by June 30, 2000 will be assured consideration.

In accordance with Canadian Immigration requirements, this advertisement
is directed towards Canadian citizens and permanent residents of
Canada. Memorial University of Newfoundland is committed to employment
equity. Memorial University is part of a vibrant, local scientific and
engineering community which maintains an inventory of available
positions for qualified partners. Partners of candidates for positions
are invited to include their r=E9sum=E9 for possible matching with other job


From: Gustaf Soderlind <>
Date: Mon, 13 Mar 2000 12:00:00 +0100 (MET)
Subject: Faculty Position at Lund Institute of Technology

Lund Institute of Technology in Lund, Sweden, has an open
position as full professor of scientific computing. We seek
applicants having a strong record in constructing, analyzing,
developing and applying new numerical methods and mathematical
models in computational problems of importance in science and
engineering. Further information about the position is available
at the web-site

Applications are due April 19, 2000.

Gustaf Soderlind
Numerical Analysis
Center for Mathematical Sciences
Lund Univeristy
Box 118
SE-221 00 Lund, Sweden


From: Reneaume Jean-Michel <>
Date: Mon, 13 Mar 2000 09:24:42 -0000
Subject: Postdoctoral Position at ENSGTI, Pau, France

Within the SIMAPI (SIMulateur Aquitain de Procedes d'Incineration) project,
the LGPP (Laboratoire de Genie des Procedes de Pau) establishes physical
models describing incineration processes. As a background, a steady state
model for fluidised bed incinerator has been developed. The objective of
this postdoctoral position is to complete the existing model in order to
allow dynamic simulations :
* Transition from steady states.
* Start up of the process.
* Incidents on the process.
Working conditions as well as environmental impact are the two governing
variables that need to be simulated.

The LGPP has a position for one postdoc during 12 months. The beginning of
the position is planed for July 1st 2000. This laboratory is looking for a
highly-qualified researcher with a great autonomy, having background in
Chemical Engineering, process modelling, numerical methods, simulation
systems and programming.

Inquiries should be directed to Jean Michel Reneaume. Email or write with
full CV and contact details.

Jean Michel Reneaume
Rue Jules Ferry
64000 Pau France
Tel: 33 - 5 59 72 20 47
Fax: 33 - 5 59 72 20 81


From: Alfio Quarteroni <>
Date: Thu, 16 Mar 2000 11:14:14 +0100
Subject: PhD Position at EPFL

Ph.D Position at Ecole Polytechnique Federale de Lausanne

The Ecole Polytechnique Federale de Lausanne (Switzerland) is seeking
a qualified candidate for a Ph.D position funded by Swiss National
Science Foundation (FNS). The project will be coordinated by

Fluid Mechanics Laboratory Department of Mechanical
Engineering & Department of Mathematics.

The title of the proposed programme of research is

"Spectral Element Methods for Viscoelastic Flow Problems". Suitable
applicants should be qualified mathematician or engineer.
Further information about the EPF Lausanne may be found on its
web page The successful candidate will join a
thriving research-oriented Department and have access to a wide
variety of computing platforms for the duration of the project
(at least three years.)

Applications in the form of a covering letter, a full C.V. and the
contact details of three referees may be posted, faxed or emailed
(by April 15) to

Prof. Robert G.Owens,
CH-1015 Lausanne, Switzerland
Tel: ++41 21 693 3589
Fax: ++41 21 693 36 46

or to

Prof. Alfio Quarteroni,
CH-1015 Lausanne, Switzerland
Tel: ++41 21 693 5546
Fax: ++41 21 693 4303


From: Roland masson <>
Date: Thu, 16 Mar 2000 13:32:11 +0100
Subject: PhD Position at Institut Francais du Petrole, Paris

We have grants from the EC HUMAN program, for supporting European
researchers (PhDs and post-docs) in our department, in association with
our subsidiary BEICIP-FRANLAB. These grants are available now. In
particular we propose the following PhD position in scientific computing:

Domain decomposition methods for modelling hydrocarbon reservoir formation

Basin modelling aims at reconstructing the time evolution of a sedimentary
basin in order to make quantitative predictions of geological phenomena
leading to oil accumulations. It accounts for porous medium compaction,
hydrocarbon formation and migration.

Recent evolutions of basin simulators have contributed to improve
the treatment of geological discontinuities such as faults. These faults
divide the basin into blocks whose deformations cause geological layers to
slide between themselves. A natural discretization of these complex geometries
involves sliding meshes which do not match.

The goal of this PHD is to propose, to analyse and to implement adequate
numerical methods. The domain decomposition approach will be used as it enables
efficient handling of non-matching grids. Moreover, it is well suited to
parallel computing.

The candidate will join the scientific computing group of the Computer
Sciences and Applied Mathematics Department of IFP. He will work within the
basin modelling and reservoir simulation projects. Applicants should posess
some background in numerical simulation of PDE's and linear algebra as well
as programming experience in C.

To apply, send a CV and references to
Isabelle Faille, Computer Sciences and Applied Mathematics Department,
IFP, e-mail: or
to Frederic Nataf CMAPX, Ecole Polytechnique, Paris, e-mail:

Institut Francais du Petrole
1 et 4 av. de Bois-Preau, BP 311
92852 Rueil-Malmaison Cedex tel : +33 1 47 52 71 33
FRANCE fax : +33 1 47 52 70 22


From: Vaibhav Deshpande <>
Date: Thu, 16 Mar 2000 10:38:58 +0100
Subject: Visiting Positions at Swiss Center for Scientific Computing

Call for Participation in VISITING RESEARCHER PROGRAM (VRP 2000) at CSCS

As part of its educational initiative, the Swiss Center for Scientific
Computing (CSCS) has traditionally conducted two separate student
programs (SSIP and PRSS) which offered a unique opportunity to students
from within Switzerland and abroad to work on specific projects during
their stay at CSCS. From this year onwards, CSCS will organize
Visiting Researcher Program (VRP 2000). This new program, which
supersedes the two separate programs, offers additional possibilities
to not only young students but also junior and senior researchers
active in their field to broaden their horizons of knowledge and gain
unique experience during their stay at CSCS.

While interacting with experts within and outside of CSCS, invited
candidates will either carry out a project proposed by CSCS or will
have the freedom to define and conduct their own project which will be
relevant for CSCS. Topics include, but are not limited to, problems in
computational modeling, computer graphics and visualization, software
engineering and information processing.

The program will commence in July 2000 with a period of stay from a
few weeks to a maximum of 4 months. Candidates are strongly
encouraged to seek funding from indigenous sources. For those without
adequate funding, CSCS may pay a fixed stipend (up to CHF 2200
max. per month) to cover the stay and travel expenses.

The program is open to Swiss and foreign postgraduate students and
researchers with background and research interests in Computational
and/or Computer Sciences and Engineering. Undergraduate students of
exceptional merit who intend to pursue higher education in these areas
may also apply. Applications will be screened to invite a limited
number of candidates.

More details about the program and the application procedure can be
found at CSCS web site ( or by
email to The closing date is 31 March 2000 for
international applications and 30 Apr 2000 for Swiss applicants.


End of NA Digest