NA Digest Tuesday, January 2, 2007 Volume 07 : Issue 01

Today's Editor:
Tamara G. Kolda
Sandia National Labs

Submissions for NA Digest:

Mail to

Information via email about NA-NET:

Mail to


From: "Prof. T. Tang" <>
Date: Wed, 27 Dec 2006 15:06:24 +0800 (HKT)
Subject: Call for nominations for Feng Kang Prize, 2007

Call for Nominations for Feng Kang Prize

The Committee of Feng Kang Prize of Scientific Computing is seeking
applications and nominations for 2007 year. The prize is awarded every
other year to young Chinese Scientists in China and abroad for their
outstanding researches in numerical analysis and scientific computing. The
prize winners will be announced in September 2007. Application forms can
be obtained by anonymous ftp from

Deadline for applications and nominations is MARCH 15, 2007.

Please send all materials to
Ms. Ru-Juan Ding
Institute of Computational Mathematics
No.55, East Road, Zhong-Guan-Cun, Beijing 100080, CHINA


From: Tim Davis <>
Date: Fri, 29 Dec 2006 09:41:15 -0500
Subject: Wilkinson's definition of a sparse matrix

Wilkinson is said to have defined a sparse matrix as:

"any matrix with enough zeros that it pays to take advantage of them." [1]

I've also seen the quote as "... matrices that allow special
techniques to take advantage of the large number of zero elements
and the structure."

The definition is informal, but quite useful. It correctly ties
the exploitation of sparsity to the methods used to operate on the
matrix. For example, it excludes randomly generated sparse
matrices (for direct methods), since with modest assumptions a randomly
generated sparse matrix with O(n) entries requires O(n^3) time and
O(n^2) memory to factorize. No "real" sparse matrix (arising in any
application) behaves anything like that.

However, the original citation for this quote is never cited, in
any of the places I've seen it used.

Can anyone shed some light on where the quote appears, or when
Wilkinson said it? I'll summarize any information I find in a subsequent
NA Digest.

Tim Davis

[1] J. R. Gilbert, C. Moler, R. Schreiber, "Sparse Matrices
in MATLAB: Design and Implementation", SIAM J. Matrix Analysis
and Applications, vol 13, no 1, pp 333-356, 1992.


Date: Sun, 24 Dec 2006 15:40:43 -0500 (EST)
Subject: Re: Fortran vs. Matlab vs. ....

To widen the discussion further, I would like to point out that there is a
lot of "user-centred programming" going on in things like spreadsheets and
statistical packages. While R or S (statistical languages) have pretty
good numerical foundations, there are other packages that do not, for
instance, using matrix inverses rather than decompositions. This is
declining, but each new generation of workers needs re-educating. This
educational activity won't be in the NA classroom.

Worse is the almost universal application of spreadsheets e.g., for over
95% if investment decisions according to some authors. Here, apart from
some efforts by Gnumeric, there doesn't seem to be much activity in the
numeric arena.

(Conflict of interest statement: I'm working on the test sheets for
Gnumeric. Folk are welcome to contact me about this. The sheets are,
however, in .xls form to invite use by other processors.)

John Nash


From: "William E. Schiesser" <>
Date: Mon, 25 Dec 2006 20:52:27 -0500
Subject: Re; MATLAB, etc.

We read with interest the comments in NA Digest about the choice of a
programming language for teaching numerical analysis. We can also
mention that we have a publication relating to this:

Lee, H. J., et al, "Ordinary and Partial Differential Equation Routines
in C, C++, Fortran, Java, Maple and Matlab", CRC Press, Boca Raton, 2003

This book includes two ODE applications and two PDE applications (the
latter includes an analysis of the collapse of the World Trade Center
towers) programmed in the six languages. If NA Digest readers think
the programs from this book would be of interest, we will be glad to
send them (all we need is a mailing address for a small package).


W. E. Schiesser


From: Mike Sussman <>
Date: Tue, 26 Dec 2006 15:20:53 -0500
Subject: Re: Matlab and teaching numerical analysis

Victor Pereyra made a valuable distinction between teaching numerical
analysis to people who use numerical analysis as a tool and teaching
numerical analysis to specialists. However, I believe that
non-specialists and specialists alike should be taught numerical
analysis using an interactive language such as Matlab.

Scientific computing specialists surely need to learn how to use one or
more of the compiled languages suitable for large projects. Is a
numerical analysis course the correct place to teach the requisite
programming and debugging skills, though? Is numerical analysis so
lacking in subject matter that it must be combined with a programming
language in order to fill the time?

It would be better to present scientific programming languages as a
course separate from numerical analysis, focusing on linguistic issues,
debugging, parallel programming and, perhaps, data structures.
Applications, examples and language taken from scientific computing
would distinguish such a course from its siblings in theoretical
Computer Science. Separating numerical analysis from compiled languages
would better serve both those numerical analysts who do not need large
scale computing, who could skip it, and those students outside
traditional numerical analysis who do need large scale computing.

Finally, it is important for specialists in numerical analysis to know
Matlab, Mathematica, Maple, and the like. I worked for years in a
non-academic setting and I found that a considerable amount of numerical
analysis could be done quickly and efficiently in the Matlab
environment. My Matlab scripts were later converted into Fortran under
two conditions: (1) when computing requirements exceeded the resources
available on the platforms that support Matlab; and (2) when the
algorithm was needed as part of a larger project. And even that
conversion profited from my Matlab experience both in better code
organization and also debugging, since I had working code for

Mike Sussman


From: Tim Davis <>
Date: Thu, 28 Dec 2006 11:29:11 -0500
Subject: Poem: f(U(n,1)) ... the recreational (lower left-hand) corner

Inspired by Jim Demmel's hacked version of Blake's "Tyger! Tyger!" poem...

The Tyger, by William Blake | Matryx Factyrs, by T.D.

Tyger! Tyger! burning bright | Matryx! Factyrs! left and right
In the forests of the night, | In space R to n affright,
What immortal hand or eye | What LU, Chol, QR, try
Could frame thy fearful symmetry? | To keep thy fearful symmetry?

In what distant deeps or skies | In what MATLAB workspace keep
Burnt the fire of thine eyes? | thine entries vast, thy SVD?
On what wings dare he aspire? | On what code dare he aspire?
What the hand dare seize the fire? | As thy pivots grow yet higher?

And what shoulder, and what art, | And what Householder reflection
Could twist the sinews of thy heart? | Could keep error bounds perfection?
And when thy heart began to beat, | When thy eigenvalues beat,
What dread hand? and what dread feet? | Can we reconstruct thy shape?

What the hammer? what the chain? | What the etree? what the path?
In what furnace was thy brain? | In what space thine eigen hath?
What the anvil? what dread grasp | What the platform? What dread code
Dare its deadly terrors clasp? | Dare its entries in core hold?

When the stars threw down their spears,| When pivots threw down their cliques,
And water'd heaven with their tears, | And maxed out memory with their fill,
Did he smile his work to see? | Did he smile his work to see?
Did he who made the Lamb make thee? | Did he code UMFPACK just for thee?

Tyger! Tyger! burning bright | Matryx! Factyrs! left and right
In the forests of the night, | In space R to n affright,
What immortal hand or eye | What LU, Chol, QR, try
Could frame thy fearful symmetry? | To keep thy fearful symmetry?


From: gerhardwilhelm weber <>
Date: Tue, 02 Jan 2007 08:36:17 +0200
Subject: INFORMS International 2007 in Puerto Rico, July 8-11, 2007

Puerto Rico, July 8-11, 2007

1. Submit an Abstract; Deadline February 1, 2007
2. Organize a Cluster or Session
3. Subdivision-Sponsored Clusters
4. Many New Topics and Special Clusters Planned
5. Spectacular Resort Location
6. Full Social Program - Learn to Salsa!

1. Submit an Abstract; Deadline February 1, 2007

We invite you to join us at INFORMS International Puerto Rico
2007, July 8-11. It's an opportunity to present your work at this
prestigious INFORMS international meeting, allowing you to keep
abreast of the latest developments in the field and, at the same
time, experience the vibrant beauty and culture of this tropical
island. Operations researchers and affiliated professionals from
Central and South America are particularly encouraged to attend
and present their work. To submit an abstract, go to:

2. Organize a Cluster or Session

The program is well underway, however, there is still time to
participate. New ideas for invited sessions are welcome.
Contact the Program Chair, Robin Lougee-Heimer
( for more information.

3. Subdivision-Sponsored Clusters

Many INFORMS subdivisions are organizing specialized tracks.
For a list of subdivision clusters and chairs go to

4. Many New Topics and Special Clusters Planned

The scientific program will cover the broad O.R. landscape. New
features include special clusters on O.R. in the Americas, O.R.
at the Edge, industry's unsolved problems, new O.R. techniques
for manufacturing, managing health care, O.R. in retail marketing,
and many other emerging areas. For a complete list of topics, go

5. Spectacular Resort Location

The conference location, the Westin Rio Mar Beach Resort & Spa,
is the most luxurious hotel on the island, with 500 acres of tropical
paradise on the island's northeast shore, adjacent to El Yunque
National Forest. The resort features a mile of uninterrupted beach,
multiple swimming pools, a water sports center, spa, casino,
tennis courts, golf courses, and much more. The special INFORMS
rate is $170.50 single/double occupancy. We have also reserved
a block of rooms at the El Conquistador, another world-class
resort hotel, 20

From: Hershkowitz Daniel <>
Date: Thu, 28 Dec 2006 22:24:59 +0200 (IST)
Subject: Contents, ELA 15

Volume 15 (2006) of ELA - ELECTRONIC Journal of LINEAR ALGEBRA is now
complete. Here is its table of contents.

1. Eduardo Marques de Sa, Some subpolytopes of the Birkhoff polytope, pp.

2. Zhi-Gang Ren, Ting-Zhu Huang and Xiao-Yu Cheng, A note on generalized
Perron complements of Z-matrices, pp. 8-13.

3. Wenchang Chu, The Cauchy double alternant and divided differences, pp.

4. Leiba Rodman, Bounded and stably bounded palindromic difference
equations of first order, pp. 22-49.

5. Christian Mehl, On classification of normal matrices in indefinite
inner product spaces, pp. 50-83.

6. Christian Mehl, Essential decomposition of polynomially normal matrices
in real indefinite inner product spaces, pp. 84-106.

7. Efstathios N. Antoniou and Stavros Vologiannidis, Linearizations of
polynomial matrices with symmetries and their applications, pp. 107-114.

8. Said Kouachi, Eigenvalues and eigenvectors of tridiagonal matrices, pp.

9. Mouhamad Al Sayed Ali and Miloud Sadkane, On a Lyapunov type equation
related to parabolic spectral dichotomy, pp. 134-142.

10. Michael Karow, Eigenvalue condition numbers and a formula of Burke,
Lewis and Overton, pp. 143-153.

11. Ilya M. Spitkovsky, On polynomials in two projections, pp. 154-158.

12. Francoise Tisseur and Stef Graillat, Structured condition numbers and
backward errors in scalar product spaces, pp. 159-177.

13. R. Ben Taher, M. Mouline and Mustapha Rachidi, Fibonacci-Horner
decomposition of the matrix exponential and the fundamental system of
solutions, pp. 178-190.

14. Marek Niezgoda, Upper bounds on certain functionals defined on groups
of linear operators, pp. 191-200.

15. Rafael Bru, Francisco Pedroche and Daniel B. Szyld, Subdirect sums of
S-strictly diagonally dominant matrices, pp. 201-209.

16. Guoli Ding and Andrei Kotlov, On minimal rank over finite fields, pp.

17. Ting-Zhu Huang, Wei Zhang and Shu-Qian Shen, Regions containing
eigenvalues of a matrix, pp. 215-224.

18. Semitransitivity Working Group at LAW'05, Bled, Semitransitive
subspaces of matrices, pp. 225-238. Working group members: Janez Bernik,
Roman Drnovsek, Don Hadwin, Ali Jaffarian, Damjana Kokol Bukovsek, Tomaz
Kosir, Marjeta Kramar Fijavz, Thomas Laffey, Leo Livshits, Mitja Mastnak,
Roy Meshulam, Vladimir Muller, Eric Nordgren, Jan Okninski, Matjaz
Omladic, Heydar Radjavi, Ahmed Sourour and Richard Timoney

19. Maria Adam and Michael J. Tsatsomeros, An eigenvalue inequality and
spectrum localization for complex matrices, pp. 239-250.

20. Albrecht Boettcher, Schatten norms of Toeplitz matrices with
Fisher-Hartwig singularities, pp. 251-259.

21. Ahmad M. Hasani and Mehdi Radjabalipour, The structure of linear
operators strongly preserving majorizations of matrices, pp. 260-268.

22. Wei Zhang and Zheng-zhi Han, Bounds for the spectral radius of block
H-matrices, pp. 269-273.

23. Karl-Heinz Foerster and Bela Nagy, Irreducible Toeplitz and Hankel
matrices, pp. 274-284.

24. Stephen W. Drury, Essentially Hermitian matrices revisited, pp.

25. Stefano De Leo, Gisele Ducati and Vinicius Leonardi, Zeros of
unilateral quaternionic polynomials, pp. 297-313.

26. Michael Neumann and Jianhong Xu, A note on Newton and Newton-like
inequalities for M-matrices and for Drazin inverses of M-Matrices, pp.

27. Vladimir Nikiforov, Linear combinations of graph eigenvalues, pp.

28. Stephen J. Kirkland, Limit points for normalized Laplacian
eigenvalues, pp. 337-344.


From: Claude Brezinski <>
Date: Tue, 26 Dec 2006 12:12:25 +0100
Subject: Contents, Numerical Algorithms

Numerical Algorithms
Volume 42, Number 3-4

Michele Benzi, Ljiljana Cvetkovic, Michael Neumann
205 - 206

A modified damped Newton method for linear complementarity problems
Zhong-Zhi Bai, Jun-Liang Dong
207 - 228

H-matrix theory vs. eigenvalue localization
Ljiljana Cvetkovic
229 - 245

Bounds for the Perron root, singularity/nonsingularity conditions, and
eigenvalue inclusion sets
Lilia Yu. Kolotilina
247 - 280

Transformation of high order linear differential-algebraic systems to
first order
Volker Mehrmann, Chunchao Shi
281 - 307

The many proofs of an identity on the norm of oblique projections
Daniel B. Szyld
309 - 323

New subclasses of block H-matrices with applications to parallel
decomposition-type relaxation methods
Ljiljana Cvetkovic, Vladimir Kostic
325 - 334

On matrices with operator entries
Ljiljana Cvetkovic, Djurdjica Takaci
335 - 344

Interpolation algorithm of Leverrier-Faddev type for polynomial matrices
Marko D. Petkovic, Predrag S. Stanimirovic
345 - 361

On the convergence of the sequences of Gerschgorin-like disks
Miodrag S. Petkovic, Ljiljana D. Petkovic
363 - 377

Numerical Algorithms
Volume 43, Number 1

On the fast solution of Toeplitz-block linear systems arising in
multivariate approximation theory
Stefan Becuwe, Annie Cuyt
1 - 24

A spectrally accurate algorithm for electromagnetic scattering in
three dimensions
M. Ganesh, S. C. Hawkins
25 - 60

Least-squares spectral collocation with the overlapping Schwarz method
for the incompressible Navier-Stokes equations
Wilhelm Heinrichs
61 - 73

The mixed directional difference-summation algorithm for generating
the Bézier net of a trivariate four-direction Box-spline
G. Casciola, E. Franchini, L. Romani
75 - 98

One-leg variable-coefficient formulas for ordinary differential
equations and local-global step size control
Gennady Yu. Kulikov, Sergey K. Shindin
99 - 121

End of NA Digest