Osni Marques
Address:
Lawrence Berkeley National Laboratory
1 Cyclotron Road, MS 50F-1650
Berkeley, CA 94720-8139, USA
E-mail: OAMarques_at_lbl.gov
Phone: (510) 486-5290
Fax: (510) 486-5812

Interests


Selected Publications


Applications

Inverse Problems in Earth Sciences

The problems described here resulted from a collaboration with Don Vasco, (LBNL/Earth Sciences Division). In this collaboration, we investigated tools for the solution of large inverse problems from applications in Geophysics; namely in the study of a physical model for the internal structure of the Earth. In this study, a linear model for the Earth structure is obtained by discretizing the Earth into layers, and the layers into cells. The velocity of wave propagation in each cell is represented by a set of parameters that account for anisotropy, location (and correction) of sources and receivers, etc. These parameters are written in matrix form and the goal is to fit the model by means of some known data. Travel times of sound waves generated by earthquakes are used to construct the model. The validation of the model requires the computation of an approximate generalized inverse and a (partial) singular value decomposition (SVD) is used for that purpose. The SVD is also used to estimate resolution and uncertainties.

The following table lists some of the numerical models that have been studied, where m is number of travel times (number of rows in the matrix), n is the number of parameters in the model (number of columns in the matrix) and nnz is the number of nonzero entries in the corresponding matrix. A block Lanczos algorithm was used to compute a rank-k SVD approximation for the models. Although sparse, such problems are difficult to deal with because several thousand singular values and singular vectors may be required for a proper estimation of the model parameters and resolution. For details, see Solving Large Linear Inverse Problems in Geophysics by means of Eigenvalue Calculations and also BLZPACK.

 ----------------------------------------
model m n nnz
----------------------------------------
1 846968 96300 28587210
2 1433102 307134 51506866
3 1433102 307134 47968477
----------------------------------------

Gallery/Applications
:
Model 3. Resolution for the mantle using 10,000 Lanczos vectors for compressional waves. The picture shows the diagonal entries of the resolution matrix, R=VVT, where V contains the Lanczos approximations for the left singular vectors. Model 3. Velocity deviation estimates for the mantle using 10,000 Lanczos vectors for compressional waves.

Conformational Changes of Proteins

This was a collaboration with Yves-Henri Sanejouand (Laboratoire de Physique, ENS Lyon). The goal was to study conformational changes of proteins by means of linear combinations of normal modes coordinates. These coordinates are obtained from solutions of an eigenvalue problem Ax=x, where A is a symmetric matrix computed from the potential energy and the atomic masses of the protein. The following table lists some cases that have been studied, where n is the dimension of the matrix A (three times the number of atoms) and nnz is the number of nonzero entries in the upper triangle of A. For details, see Protein Motions through Eigenanalyses: A Set of Study Cases and also BLZPACK. Later, Yves-Henri and collaborators proposed a simplified method, RTB (rotations-translations of blocks), to study conformation changes of proteins. For most cases, this method can significantly speed up the calculations of the low-frequency normal modes that are usually required in the analyses, without loss of accuracy. The software can be obtained from Yves-Henri.

 ----------------------------------------
protein n nnz
----------------------------------------
crambin 1188 134217
lysozyme 3795 490602
ras_p21A 4986 669060
ras_p21B 4998 677832
ras_p21C 4998 698973
ras_p21D 4986 691776
arabinose 8592 1161360
citrate synthase 25584 3691020
----------------------------------------

Gallery/Applications:

Simplified model of the maltodextrin binding protein (370 residues) and animation of the first mode shape (hinge-bending motion, closure of the binding site) using the RTB method. The picture shows the "effective residues" (one sphere per amino-acid) and the corresponding bonds (between neighbors).
Simplified model of the LAO binding protein (238 residues) and animation of the first mode shape (hinge-bending motion, closure of the binding site) using the RTB method. The picture shows the "effective residues" (one sphere per amino-acid) and the corresponding bonds (between neighbors).
Three representations of crambin (ball-and-stick, ribbon and Van der Waals), which is a protein found in some seeds. The model shown comprises 396 atoms.
Original upper triangle, reverse Cuthill-McKee and symmetric minimum degree ordering of the matrix corresponding to the numerical model used for crambin. The matrix has dimension 1188 and 134217 non zeros in its upper triangle, including the diagonal.
Ribbon representation of ras, which is a protein related with the transmission of biochemical information between the surface of the cell and its nucleus (mutations in human ras genes are responsible for up to one third of all cases of cancer, see Just obeying orders, by S. Day, New Scientist, 27 May 1995), and the upper triangle of the matrix corresponding to the numerical model for ras (1662 atoms, dimension 4986 and 669060 non zeros in its upper triangle, including the diagonal).
Ribbon representation of the protein pig heart citrate synthase (two views of the open form). For details, see Hinge-Bending Motion in Citrate Synthase Arising from Normal Modes Calculations.

Information Retrieval

In 1997-1998 I collaborated with Mike Palmer, from Inktomi Inc, in the investigation of matrix methods for information retrieval on sets of documents obtained from the World Wide Web. The dimension of one of the term-document matrices examined was 100,000 (number of terms or words) by 2,559,430 (number of documents or home pages), which contained 421 million nonzero entries. One of our eigenvalue solvers (BLZPACK) was used to compute singular values and singular vectors of this matrix. To the best of our knowledge, at the time it was the largest matrix for which a (partial) singular value decomposition had been computed. The computation of 10 singular values and left singular vector required 710 seconds of wall clock time on 64 processors of a Cray T3E-900 (900 Mflops/PE, 256 MB/PE): 99.5% of that time was spent with matrix-vectors multiplications (for the generation of Lanczos vectors). For details about information retrieval and related topics see Michael Berry's LSI Web Site, the LSA Web Site at CU Boulder, and also some of the papers written by Jon Kleinberg and Inderjit Dhillon.

Gallery/Applications:

Singular value distribution of the 100,000-by-2,559,430 term-document matrix (54 steps of the Lanczos algorithm). First two singular vectors of he 100,000-by-2,559,430 term-document matrix (54 steps of the Lanczos algorithm).

Tools for Spectral Portrait Computations

This work was carried out at in collaboration with the Qualitative Computing Group (led by Prof. Francoise Chaitin-Chatelin) of the Parallel Algorithms Project (led by Prof. Iain Duff) at CERFACS. The goal was to develop tools for the computation of pseudospectra of linear operators. For details, see Spectral Portrait Computation by a Lanczos Method (augmented and normal matrix versions). See also Pseudospectra of Linear Operators by Nick Trefethen, SIAM Review, 39:383-406, 1997, and the Matrix Market page on spectral portraits.

Gallery/Applications:

Spectral portrait of the La Rose matrix (65536 grid points). Spectral portrait of the Tolosa matrix (18225 grid points).

Structural Engineering Problems

In my Ph.D. work at COPPE, Federal University of Rio de Janeiro, Brazil, I studied reduced basis techniques for the solution of systems of partial differential equations, and algorithms for the solution of large sparse eigenvalue problems. These problems arise very often in Structural Engineering Finite Element analyses. During the thesis I was a Research Associate with PETROBRAS (The Brazilian Petroleum Company) and also worked as a consultant for INPE (Brazilian Institute for Spatial Research), using the MSC/NASTRAN code.

Gallery/Applications:

Double-cross with frequencies distributed in clusters (see Selected Results from the NAFEMS, Dynamics Working Group Free Vibrations, Benchmarks, Part 1, by A. Morris, Benchmarks, April 1987). The finite element model used comprises 321 nodes, 320 2D beam elements and 947 degrees of freedom.

Self-elevating drilling unit designed for operation up to 100m water depth. The finite element model used comprises 90 nodes, 96 3D beam elements and 531 degrees of freedom.
Steel jacket platform designed for 170m water depth. The finite element model comprises 437 nodes, 1097 3D beam elements and 2463 degrees of freedom.

Software

The development of the software listed below was required in the context of the problems I have worked on. The codes are stored in gzipped tar files and also winzip files. In case of download problems or questions about the codes just send me an e-mail. The release date is given as a reference since I may update the codes from time to time.


Lawrence Berkeley National Laboratory Computational Research Division Resume