Friday, July 23rd 2004

organized by CMUC
Coimbra - Portugal

Welcome to the web site of the Advanced Seminar Day on Computational Science, which will take place at the Department of Mathematics (Pedro Nunes Room) of the University of Coimbra, Portugal. This is a one-day short course lectured by Erik Elmroth of the Department of Computing Science of Umeå University (Sweden)  and Beatrice Meini from the Department of Mathematics of the University of Pisa (Italy).

The short course will take place the day immediately after the 11th Conference of the International Linear Algebra Society at the University of Coimbra and will be scheduled as follows:

Erik Elmroth first talk will be on recursive algorithms for improving high performance linear algebra software. Recursion allows for efficient utilization of a memory hierarchy and generalizes existing fixed blocking by introducing automatic variable blocking that has the potential of matching every level of a deep memory hierarchy. Novel recursive blocked algorithms offer new ways to compute factorizations such as Cholesky and QR and to solve matrix equations. In fact, the whole gamut of existing dense linear algebra factorization is beginning to be re-examined in view of the recursive paradigm. This work has recently been presented in a survey article in the current issue of SIAM Review (Vol 46, No 1, March 2004, .pdf, .ps).

His second talk will be on Grid computing. The Grid is basically the next infrastructure for computing, enabling dynamic sharing of IT-resources of all kinds, even though its current use is very much focused on building virtual supercomputers and on using idle pc:s for solving large trivially parallel problems. Main Grid Computing projects he is involved in are, e.g., (1) research for a Grid resource broker: a software tool that dynamically identifies and characterizes what resources (computers) are available and best suited for a user's particular application, selects these resources, runs the program and delivers the result where the user have requested; (2) a grid accounting system: a system for tracking grid-wide usage of resources, allowing for some kind of cost-compensation/payment; (3) Grid portals: General portals for accessing supercomputers from standard web-interfaces, and application-specific portals, e.g., for using a specific software (such as the SLICOT library) from a web-interface. Most of these developments are primarily tested in the Swegrid (www.swegrid.se) and NorduGrid (www.nordugrid.org) grid environments.

Beatrice Meini will talk about the numerical solution of certain Markov chains which model queueing problems. A Markov chain is defined by means of its probability transition matrix P, which is a nonnegative row stochastic matrix. P may be a finite or an infinite matrix, and may have a particular structure, according to the features of the queueing model which is described by the Markov chain. The fundamental problem is the computation of the steady state vector, namely of the vector x such that x^TP=x^T, normalized so that the sum of all the components of x is equal to one. Markov chains of M/G/1 type, introduced by M.F. Neuts in the 60's, model a large variety of queueing problems, and are defined by an infinite probability transition matrix P, which is block Hessenberg, and which is "almost" block Toeplitz, i.e., except for the first block row, P has constant block entries along each block diagonal. For the special structure of P, the computation of the vector x can be ultimately reduced to the solution of a nonlinear matrix equation. In the first talk, after a short introduction to general Markov chains and to Markov chains of M/G/1 type, the problem of the computation of x and of the numerical solution of the associated nonlinear matrix equation will be considered; in particular, for the latter problem, convergence of fixed point iterations will be analyzed by using the Perron-Frobenius theory on nonnegative matrices and the properties of regular splittings of M-matrices. The subject of the second talk will be the analysis of quadratically convergent methods for solving the nonlinear matrix equation; particular attention will be addressed to a method based on the technique of cyclic reduction, which has fast convergence, low computational cost (if implemented with FFTs) and good stability properties. Finally, some numerical methods for computing the steady state vector x of Tree-like stochastic processes will be presented; in this case P is an infinite matrix which is recursively defined in terms of infinite blocks; by exploiting the structure of P, also for this class of problems the computation of x is reduced to the solution of a nonlinear matrix equation, which is more complicated than the one arising in M/G/1 type Markov chains.

Everyone interested in attending should send an email message to Rute Andrade rute@mat.uc.pt simply mentioning the interest in attending. Enrollment is free.

Last change: June 25th 2004 by João Soares