Alternatives for parallel Krylov subspace basis computation

Numerical methods related to Krylov subspaces are widely used in large sparse numerical linear algebra. Vectors in these subspaces are manipulated via their representation onto orthonormal bases. Nowadays, on serial computers, the method of Arnoldi is considered as a reliable technique for constructing such bases. However, although easily parallelizable, this technique is not as scalable as expected for communications. In this work we examine alternative methods aimed at overcoming this drawback. Since they retrieve upon completion the same information as Arnoldi's algorithm does, they enable us to design a wide family of stable and scalable Krylov approximation methods for various parallel environments. We present timing results obtained from their implementation on two distributed-memory multiprocessor supercomputers: the Intel Paragon and the IBM Scalable POWERparallel SP2. (C) 1997 by John Wiley & Sons, Ltd.

Intrinsic subspace convergence in TDD MIMO communication

In numerical linear algebra, students encounter earlythe iterative power method, which finds eigenvectors of a matrixfrom an arbitrary starting point through repeated normalizationand multiplications by the matrix itself. In practice, more sophisticatedmethods are used nowadays, threatening to make the powermethod a historical and pedagogic footnote. However, in the contextof communication over a time-division duplex (TDD) multipleinputmultiple-output (MIMO) channel, the power method takes aspecial position. It can be viewed as an intrinsic part of the uplinkand downlink communication switching, enabling estimationof the eigenmodes of the channel without extra overhead. Generalizingthe method to vector subspaces, communication in thesubspaces with the best receive and transmit signal-to-noise ratio(SNR) is made possible. In exploring this intrinsic subspace convergence(ISC), we show that several published and new schemes canbe cast into a common framework where all members benefit fromthe ISC.

Identificação dos parâmetros modais utilizando apenas as respostas da estrutura: identificação no domínio do tempo

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

QRT: A Qr-based tridiagonalization algorithm for nonsymmetric matrices

The stable similarity reduction of a nonsymmetric square matrix to tridiagonal form has been a long-standing problem in numerical linear algebra. The biorthogonal Lanczos process is in principle a candidate method for this task, but in practice it is confined to sparse matrices and is restarted periodically because roundoff errors affect its three-term recurrence scheme and degrade the biorthogonality after a few steps. This adds to its vulnerability to serious breakdowns or near-breakdowns, the handling of which involves recovery strategies such as the look-ahead technique, which needs a careful implementation to produce a block-tridiagonal form with unpredictable block sizes. Other candidate methods, geared generally towards full matrices, rely on elementary similarity transformations that are prone to numerical instabilities. Such concomitant difficulties have hampered finding a satisfactory solution to the problem for either sparse or full matrices. This study focuses primarily on full matrices. After outlining earlier tridiagonalization algorithms from within a general framework, we present a new elimination technique combining orthogonal similarity transformations that are stable. We also discuss heuristics to circumvent breakdowns. Applications of this study include eigenvalue calculation and the approximation of matrix functions.

Linear instability of orthogonal compressible leading-edge boundary layer flow

Instability analysis of compressible orthogonal swept leading-edge boundary layer flow was performed in the context of BiGlobal linear theory. 1, 2 An algorithm was developed exploiting the sparsity characteristics of the matrix discretizing the PDE-based eigenvalue problem. This allowed use of the MUMPS sparse linear algebra package 3 to obtain a direct solution of the linear systems associated with the Arnoldi iteration. The developed algorithm was then applied to efficiently analyze the effect of compressibility on the stability of the swept leading-edge boundary layer and obtain neutral curves of this flow as a function of the Mach number in the range 0 ≤ Ma ≤ 1. The present numerical results fully confirmed the asymptotic theory results of Theofilis et al. 4 Up to the maximum Mach number value studied, it was found that an increase of this parameter reduces the critical Reynolds number and the range of the unstable spanwise wavenumbers.

A parallel numerical solver using hierarchically tiled arrays

Solving linear systems is an important problem for scientific computing. Exploiting parallelism is essential for solving complex systems, and this traditionally involves writing parallel algorithms on top of a library such as MPI. The SPIKE family of algorithms is one well-known example of a parallel solver for linear systems. The Hierarchically Tiled Array data type extends traditional data-parallel array operations with explicit tiling and allows programmers to directly manipulate tiles. The tiles of the HTA data type map naturally to the block nature of many numeric computations, including the SPIKE family of algorithms. The higher level of abstraction of the HTA enables the same program to be portable across different platforms. Current implementations target both shared-memory and distributed-memory models. In this thesis we present a proof-of-concept for portable linear solvers. We implement two algorithms from the SPIKE family using the HTA library. We show that our implementations of SPIKE exploit the abstractions provided by the HTA to produce a compact, clean code that can run on both shared-memory and distributed-memory models without modification. We discuss how we map the algorithms to HTA programs as well as examine their performance. We compare the performance of our HTA codes to comparable codes written in MPI as well as current state-of-the-art linear algebra routines.

Lanczos algorithm on the grassmann manifold

5th. European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2008) 8th. World Congress on Computational Mechanics (WCCM8)

Spectral Analysis of Bounded Self-adjoint operators - A Linear Algebraic Approach

This thesis Entitled Spectral theory of bounded self-adjoint operators -A linear algebraic approach.The main results of the thesis can be classified as three different approaches to the spectral approximation problems. The truncation method and its perturbed versions are part of the classical linear algebraic approach to the subject. The usage of block Toeplitz-Laurent operators and the matrix valued symbols is considered as a particular example where the linear algebraic techniques are effective in simplifying problems in inverse spectral theory. The abstract approach to the spectral approximation problems via pre-conditioners and Korovkin-type theorems is an attempt to make the computations involved, well conditioned. However, in all these approaches, linear algebra comes as the central object. The objective of this study is to discuss the linear algebraic techniques in the spectral theory of bounded self-adjoint operators on a separable Hilbert space. The usage of truncation method in approximating the bounds of essential spectrum and the discrete spectral values outside these bounds is well known. The spectral gap prediction and related results was proved in the second chapter. The discrete versions of Borg-type theorems, proved in the third chapter, partly overlap with some known results in operator theory. The pure linear algebraic approach is the main novelty of the results proved here.

ELEC3035: Control System Design

Lecture slides, handouts for tutorials, exam papers, and numerical examples for a third year course on Control System Design.

Análisis de sensibilidad para un modelo de medición de percepción de marca basado en simulación computacional por agentes

Se presenta el análisis de sensibilidad de un modelo de percepción de marca y ajuste de la inversión en marketing desarrollado en el Laboratorio de Simulación de la Universidad del Rosario. Este trabajo de grado consta de una introducción al tema de análisis de sensibilidad y su complementario el análisis de incertidumbre. Se pasa a mostrar ambos análisis usando un ejemplo simple de aplicación del modelo mediante la aplicación exhaustiva y rigurosa de los pasos descritos en la primera parte. Luego se hace una discusión de la problemática de medición de magnitudes que prueba ser el factor más complejo de la aplicación del modelo en el contexto práctico y finalmente se dan conclusiones sobre los resultados de los análisis.

Perturbation, extraction and refinement of invariant pairs for matrix polynomials

Generalizing the notion of an eigenvector, invariant subspaces are frequently used in the context of linear eigenvalue problems, leading to conceptually elegant and numerically stable formulations in applications that require the computation of several eigenvalues and/or eigenvectors. Similar benefits can be expected for polynomial eigenvalue problems, for which the concept of an invariant subspace needs to be replaced by the concept of an invariant pair. Little has been known so far about numerical aspects of such invariant pairs. The aim of this paper is to fill this gap. The behavior of invariant pairs under perturbations of the matrix polynomial is studied and a first-order perturbation expansion is given. From a computational point of view, we investigate how to best extract invariant pairs from a linearization of the matrix polynomial. Moreover, we describe efficient refinement procedures directly based on the polynomial formulation. Numerical experiments with matrix polynomials from a number of applications demonstrate the effectiveness of our extraction and refinement procedures.

Feedback design for regularizing descriptor systems

This paper surveys numerical techniques for the regularization of descriptor (generalized state-space) systems by proportional and derivative feedback. We review generalizations of controllability and observability to descriptor systems along with definitions of regularity and index in terms of the Weierstraß canonical form. Three condensed forms display the controllability and observability properties of a descriptor system. The condensed forms are obtained through orthogonal equivalence transformations and rank decisions, so they may be computed by numerically stable algorithms. In addition, the condensed forms display whether a descriptor system is regularizable, i.e., when the system pencil can be made to be regular by derivative and/or proportional output feedback, and, if so, what index can be achieved. Also included is a a new characterization of descriptor systems that can be made to be regular with index 1 by proportional and derivative output feedback.

Modal coupling in linear control systems using robust eigenstructure assignment

Eigenvalue assignment methods are used widely in the design of control and state-estimation systems. The corresponding eigenvectors can be selected to ensure robustness. For specific applications, eigenstructure assignment can also be applied to achieve more general performance criteria. In this paper a new output feedback design approach using robust eigenstructure assignment to achieve prescribed mode input and output coupling is described. A minimisation technique is developed to improve both the mode coupling and the robustness of the system, whilst allowing the precision of the eigenvalue placement to be relaxed. An application to the design of an automatic flight control system is demonstrated.

Minimum norm regularization of descriptor systems by mixed output feedback

We study the regularization problem for linear, constant coefficient descriptor systems Ex' = Ax+Bu, y1 = Cx, y2 = Γx' by proportional and derivative mixed output feedback. Necessary and sufficient conditions are given, which guarantee that there exist output feedbacks such that the closed-loop system is regular, has index at most one and E+BGΓ has a desired rank, i.e., there is a desired number of differential and algebraic equations. To resolve the freedom in the choice of the feedback matrices we then discuss how to obtain the desired regularizing feedback of minimum norm and show that this approach leads to useful results in the sense of robustness only if the rank of E is decreased. Numerical procedures are derived to construct the desired feedback gains. These numerical procedures are based on orthogonal matrix transformations which can be implemented in a numerically stable way.