Sequences of matrices arise in many applications in science and engineering. In this thesis we consider matrices that are closely related (or closely related in groups), and we take advantage of the small differences between them to efficiently solve sequences of linear systems and eigenproblems. Recycling techniques, such as recycling preconditioners or subspaces, are popular approaches for reducing computational cost. In this thesis, we introduce two novel approaches for recycling previously computed information for a subsequent system or eigenproblem, and demonstrate good results for sequences arising in several applications. Preconditioners are often essential for fast convergence of iterative methods. However, computing a good preconditioner can be very expensive, and when solving a sequence of linear systems, we want to avoid computing a new preconditioner too often. Instead, we can recycle a previously computed preconditioner, for which we have good convergence behavior of the preconditioned system. We propose an update technique we call the sparse approximate map, or SAM update, that approximately maps one matrix to another matrix in our sequence. SAM updates are very cheap to compute and apply, preserve good convergence properties of a previously computed preconditioner, and help to amortize the cost of that preconditioner over many linear solves. When solving a sequence of eigenproblems, we can reduce the computational cost of constructing the Krylov space starting with a single vector by warm-starting the eigensolver with a subspace instead. We propose an algorithm to warm-start the Krylov-Schur method using a previously computed approximate invariant subspace. We first compute the approximate Krylov decomposition for a matrix with minimal residual, and use this space to warm-start the eigensolver. We account for the residual matrix when expanding, truncating, and deflating the decomposition and show that the norm of the residual monotonically decreases. This method is effective in reducing the total number of matrix-vector products, and computes an approximate invariant subspace that is as accurate as the one computed with standard Krylov-Schur. In applications where the matrix-vector products require an implicit linear solve, we incorporate Krylov subspace recycling. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We consider convergence rates for GMRES applied to these matrices by identifying the sources of sensitivity. / Doctor of Philosophy / Problems in science and engineering often require the solution to many linear systems, or a sequence of systems, that model the behavior of physical phenomena. In order to construct highly accurate mathematical models to describe this behavior, the resulting matrices can be very large, and therefore the linear system can be very expensive to solve. To efficiently solve a sequence of large linear systems, we often use iterative methods, which can require preconditioning techniques to achieve fast convergence. The preconditioners themselves can be very expensive to compute. So, we propose a cheap update technique that approximately maps one matrix to another in the sequence for which we already have a good preconditioner. We then combine the preconditioner and the map and use the updated preconditioner for the current system. Sequences of eigenvalue problems also arise in many scientific applications, such as those modeling disk brake squeal in a motor vehicle. To accurately represent this physical system, large eigenvalue problems must be solved. The behavior of certain eigenvalues can reveal instability in the physical system but to identify these eigenvalues, we must solve a sequence of very large eigenproblems. The eigensolvers used to solve eigenproblems generally begin with a single vector, and instead, we propose starting the method with several vectors, or a subspace. This allows us to reduce the total number of iterations required by the eigensolver while still producing an accurate solution. We demonstrate good results for both of these approaches using sequences of linear systems and eigenvalue problems arising in several real-world applications. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We examine the convergence behavior of the iterative method GMRES when solving such a sequence of matrices.

In science and engineering, many applications require the solution of a sequence of linear systems. There are many ways to solve linear systems and we always look for methods that are faster and/or require less storage. In this dissertation, we focus on solving these systems with Krylov subspace methods and how to obtain effective preconditioners inexpensively. We first present an application for electronic structure calculation. A sequence of slowly changing linear systems is produced in the simulation. The linear systems change by rank-one updates. Properties of the system matrix are analyzed. We use Krylov subspace methods to solve these linear systems. Krylov subspace methods need a preconditioner to be efficient and robust. This causes the problem of computing a sequence of preconditioners corresponding to the sequence of linear systems. We use recycling preconditioners, which is to update and reuse existing preconditioner. We investigate and analyze several preconditioners, such as ILU(0), ILUTP, domain decomposition preconditioners, and inexact matrix-vector products with inner-outer iterations. Recycling preconditioners produces cumulative updates to the preconditioner. To reduce the cost of applying the preconditioners, we propose approaches to truncate the cumulative preconditioner updates, which is a low-rank matrix. Two approaches are developed. The first one is to truncate the low-rank matrix using the best approximation given by the singular value decomposition (SVD). This is effective if many singular values are close to zero. If not, based on the ideas underlying GCROT and recycling, we use information from an Arnoldi recurrence to determine which directions to keep. We investigate and analyze their properties. We also prove that both truncation approaches work well under suitable conditions. We apply our truncation approaches on two applications. One is the Quantum Monte Carlo (QMC) method and the other is a nonlinear second order partial differential equation (PDE). For the QMC method, we test both truncation approaches and analyze their results. For the PDE problem, we discretize the equations with finite difference method, solve the nonlinear problem by Newton's method with a line-search, and utilize Krylov subspace methods to solve the linear system in every nonlinear iteration. The preconditioner is updated by Broyden-type rank-one updates, and we truncate the preconditioner updates by using the SVD finally. We demonstrate that the truncation is effective. In the last chapter, we develop a matrix reordering algorithm that improves the diagonal dominance of Slater matrices in the QMC method. If we reorder the entire Slater matrix, we call it global reordering and the cost is O(N^3), which is expensive. As the change is geometrically localized and impacts only one row and a modest number of columns, we propose a local reordering of a submatrix of the Slater matrix. The submatrix has small dimension, which is independent of the size of Slater matrix, and hence the local reordering has constant cost (with respect to the size of Slater matrix). / Ph. D.

Iterative Krylov subspace methods have proven to be efficient tools for solving linear systems of equations. In the context of ill-posed inverse problems, they tend to exhibit semiconvergence behavior making it difficult detect ``inverted noise" and stop iterations before solutions become contaminated. Regularization methods such as spectral filtering methods use the singular value decomposition (SVD) and are effective at filtering inverted noise from solutions, but are computationally prohibitive on large problems. Hybrid methods apply regularization techniques to the smaller ``projected problem" that is inherent to iterative Krylov methods at each iteration, thereby overcoming the semiconvergence behavior. Commonly, the Golub-Kahan bidiagonalization is used to construct a set of orthonormal basis vectors that span the Krylov subspaces from which solutions will be chosen, but seeking a solution in the orthonormal basis generated by the Arnoldi process (which is fundamental to the popular iterative method GMRES) has been of renewed interest recently. We discuss some of the positive and negative aspects of each process and use example problems to examine some qualities of the bases they produce. Computing optimal solutions in a given basis gives some insight into the performance of the corresponding iterative methods and how hybrid methods can contribute. / Master of Science

Controle preditivo baseado em modelos (MPC) é uma técnica de controle amplamente utilizada na indústria de processos químicos. Por outro lado, o método de identificação em subespaços (SID) tem se mostrado uma alternativa eficiente para os métodos clássicos de identificação de sistemas. Pela combinação dos conceitos de MPC e SID, surgiu, no final da década de 90, uma nova técnica de controle, denominada controle preditivo com enfoque em subespaços (SPC). Essa técnica também é conhecida como controle preditivo orientado a dados. Ela substitui por um único passo as três etapas do projeto de um MPC: a identificação do modelo, o cálculo do observador de estados e a construção das matrizes de predição. Este trabalho tem como principal objetivo revisar estudos feitos na área de SPC, aplicar esse método em sistemas típicos da indústria química e propor novos algoritmos. São desenvolvidos três algoritmos de excitação interna para o método SPC, que permitem gerar dados persistentemente excitantes enquanto um controle mínimo do processo é garantido. Esses algoritmos possibilitam aplicar identificação em malha fechada, na qual o modelo do controlador SPC é reidentificado utilizando dados previamente excitados. Os controladores SPC e SPC com excitação interna são testados e comparados ao MPC por meio de simulações em dois processos distintos. O primeiro consiste em uma coluna debutanizadora de uma unidade de destilação, para a qual são disponibilizados dois modelos lineares referentes a pontos de operação diferentes. O segundo é um reator de polimerização de estireno com dinâmica não linear, cujo modelo fenomenológico é conhecido. Os resultados dos testes indicam que o SPC é mais suscetível a ruídos de medição. Entretanto, verifica-se que esse controlador corrige perturbações nos set-points das variáveis controladas mais rapidamente que o MPC. Simulações realizadas para o SPC com excitação interna mostram que os algoritmos propostos neste trabalho excitam o sistema satisfatoriamente, de modo que modelos mais precisos são obtidos na reidentificação com os dados excitados. / Model Predictive Control (MPC) technology is widely used in chemical process industries. Subspace identification (SID) on the other hand has proven to be an efficient alternative for classical system identification methods. Based on the results from MPC and SID, it was developed in the late 90s a new control approach, called Subspace Predictive Control (SPC). This approach is also known as data-driven predictive control. In this new method, one single operation replaces the three steps in a MPC controller design: system identification, the state observer design and the predictor matrices construction. The aim of this work is to review studies in the field of SPC, to apply this technology to typical systems of chemical industry and to propose new algorithms. It is developed three internal excitation algorithms for the SPC method, which allow the system to be persistently excited while a minimal control of the process is still guaranteed. These algorithms enable the application of closedloop identification, where the SPC controller model is re-identified using the previously excited data. The SPC controller and the SPC controller with internal excitation are tested through simulation for two different processes. The first one is a debutanizer column of a distillation unit for which two linear models corresponding to two different operating points are available. The second one is a non-linear system consisting of a styrene polymerization reactor. A phenomenological model is provided for this system. Tests results indicate that SPC is more susceptible to measurement noises. However, it is noticed that SPC controller corrects perturbations on set-points faster than MPC. Simulations for the SPC with internal excitation show that the proposed algorithms sufficiently excite the system, in the sense that more precise models are obtained from the re-identification with excited data.

This thesis concerns methods of reduced complexity for electronic structure calculations.  When quantum chemistry methods are applied to large systems, it is important to optimally use computer resources and only store data and perform operations that contribute to the overall accuracy. At the same time, precarious approximations could jeopardize the reliability of the whole calculation.  In this thesis, the self-consistent field method is seen as a sequence of rotations of the occupied subspace. Errors coming from computational approximations are characterized as erroneous rotations of this subspace. This viewpoint is optimal in the sense that the occupied subspace uniquely defines the electron density. Errors should be measured by their impact on the overall accuracy instead of by their constituent parts. With this point of view, a mathematical framework for control of errors in Hartree-Fock/Kohn-Sham calculations is proposed.  A unifying framework is of particular importance when computational approximations are introduced to efficiently handle large systems. An important operation in Hartree-Fock/Kohn-Sham calculations is the calculation of the density matrix for a given Fock/Kohn-Sham matrix. In this thesis, density matrix purification is used to compute the density matrix with time and memory usage increasing only linearly with system size. The forward error of purification is analyzed and schemes to control the forward error are proposed. The presented purification methods are coupled with effective methods to compute interior eigenvalues of the Fock/Kohn-Sham matrix also proposed in this thesis.New methods for inverse factorizations of Hermitian positive definite matrices that can be used for congruence transformations of the Fock/Kohn-Sham and density matrices are suggested as well. Most of the methods above have been implemented in the Ergo quantum chemistry program. This program uses a hierarchic sparse matrix library, also presented in this thesis, which is parallelized for shared memory computer architectures. It is demonstrated that the Ergo program is able to perform linear scaling Hartree-Fock calculations. / QC 20100908

Controle preditivo baseado em modelos (MPC) é uma técnica de controle amplamente utilizada na indústria de processos químicos. Por outro lado, o método de identificação em subespaços (SID) tem se mostrado uma alternativa eficiente para os métodos clássicos de identificação de sistemas. Pela combinação dos conceitos de MPC e SID, surgiu, no final da década de 90, uma nova técnica de controle, denominada controle preditivo com enfoque em subespaços (SPC). Essa técnica também é conhecida como controle preditivo orientado a dados. Ela substitui por um único passo as três etapas do projeto de um MPC: a identificação do modelo, o cálculo do observador de estados e a construção das matrizes de predição. Este trabalho tem como principal objetivo revisar estudos feitos na área de SPC, aplicar esse método em sistemas típicos da indústria química e propor novos algoritmos. São desenvolvidos três algoritmos de excitação interna para o método SPC, que permitem gerar dados persistentemente excitantes enquanto um controle mínimo do processo é garantido. Esses algoritmos possibilitam aplicar identificação em malha fechada, na qual o modelo do controlador SPC é reidentificado utilizando dados previamente excitados. Os controladores SPC e SPC com excitação interna são testados e comparados ao MPC por meio de simulações em dois processos distintos. O primeiro consiste em uma coluna debutanizadora de uma unidade de destilação, para a qual são disponibilizados dois modelos lineares referentes a pontos de operação diferentes. O segundo é um reator de polimerização de estireno com dinâmica não linear, cujo modelo fenomenológico é conhecido. Os resultados dos testes indicam que o SPC é mais suscetível a ruídos de medição. Entretanto, verifica-se que esse controlador corrige perturbações nos set-points das variáveis controladas mais rapidamente que o MPC. Simulações realizadas para o SPC com excitação interna mostram que os algoritmos propostos neste trabalho excitam o sistema satisfatoriamente, de modo que modelos mais precisos são obtidos na reidentificação com os dados excitados. / Model Predictive Control (MPC) technology is widely used in chemical process industries. Subspace identification (SID) on the other hand has proven to be an efficient alternative for classical system identification methods. Based on the results from MPC and SID, it was developed in the late 90s a new control approach, called Subspace Predictive Control (SPC). This approach is also known as data-driven predictive control. In this new method, one single operation replaces the three steps in a MPC controller design: system identification, the state observer design and the predictor matrices construction. The aim of this work is to review studies in the field of SPC, to apply this technology to typical systems of chemical industry and to propose new algorithms. It is developed three internal excitation algorithms for the SPC method, which allow the system to be persistently excited while a minimal control of the process is still guaranteed. These algorithms enable the application of closedloop identification, where the SPC controller model is re-identified using the previously excited data. The SPC controller and the SPC controller with internal excitation are tested through simulation for two different processes. The first one is a debutanizer column of a distillation unit for which two linear models corresponding to two different operating points are available. The second one is a non-linear system consisting of a styrene polymerization reactor. A phenomenological model is provided for this system. Tests results indicate that SPC is more susceptible to measurement noises. However, it is noticed that SPC controller corrects perturbations on set-points faster than MPC. Simulations for the SPC with internal excitation show that the proposed algorithms sufficiently excite the system, in the sense that more precise models are obtained from the re-identification with excited data.

The electrical motors parameters identification is solved in this master’s thesis using subspace based methods. Electrical motors are simulated in Matlab/Simulink interactive environment, specifically permanent magnet DC motor and permanent magnet synchronous motor. Identification is developed in Matlab interactive environment. Different types of subspace algorithms are used for the estimation of parameters. Results of subspace parameters estimation are compared with least squares parameters estimation. The thesis describes subspace method, types of subspace algorithms, used electrical motors, nonlinear approach of identification and comparation of parameters identification.

Phased array feeds (PAFs) are a promising new technology for astronomical radio telescopes. While PAFs have been used in other fields, the demanding sensitivity and calibration requirements in astronomy present unique new challenges. This dissertation presents some of the first astronomical PAF results demonstrating the lowest noise temperature and highest sensitivity at the time (66 Kelvin and 3.3 m^2/K, respectively), obtained using a narrowband (425 kHz bandwidth) prototype array of 19 linear co-polarized L-band dipoles mounted at the focus of the Green Bank 20 Meter Telescope at the National Radio Astronomy Observatory (NRAO) in Green Bank, West Virginia. Results include spectral line detection of hydroxyl (OH) sources W49N and W3OH, and some of the first radio camera images made using a PAF, including an image of the Cygnus X region. A novel array Y-factor technique for measuring the isotropic noise response of the array is shown along with experimental measurements for this PAF. Statistically optimal beamformers (Maximum SNR and MVDR) are used throughout the work. Radio-frequency interference (RFI) mitigation is demonstrated experimentally using spatial cancelation with the PAF. Improved RFI mitigation is achieved in the challenging cases of low interference-to-noise ratio (INR) and moving interference by combining subspace projection (SP) beamforming with a polynomial model to track a rank 1 subspace. Limiting factors in SP are investigated including sample estimation error, subspace smearing, noise bias, and spectral scooping; each of these factors is overcome with the polynomial model and prewhitening. Numerical optimization leads to the polynomial subspace projection (PSP) method, and least-squares fitting to the series of dominant eigenvectors over a series of short term integrations (STIs) leads to the eigenvector polynomial subspace projection (EPSP) method. Expressions for the gradient, Hessian, and Jacobian are given for use in numerical optimization. Results are given for simulated and experimental data, demonstrating deeper beampattern nulls by 6 to 30dB. To increase the system bandwidth toward the hundreds of MHz bandwidth required by astronomers for a fully science-ready instrument, an FPGA digital backend is introduced using a 64-input analog-to-digital converter running at 50 Msamp/sec and the ROACH processing board developed at the University of California, Berkeley. International efforts to develop digital back ends for large antenna arrays are considered, and a road map is proposed for development of a hardware correlator/beamformer at BYU using three ROACH boards communicating over 10 gigabit Ethernet.

No description available.

Thesis (MSc)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: In several numerical approaches to PDEs shifted linear systems of the form (zI - A)x = b, need to be solved for several values of the complex scalar z. Often, these linear systems are large and sparse. This thesis investigates efficient numerical methods for these systems that arise from a contour integral approximation to PDEs and compares these methods with direct solvers. In the first part, we present three model PDEs and discuss numerical approaches to solve them. We use the first problem to demonstrate computations with a dense matrix, the second problem to demonstrate computations with a sparse symmetric matrix and the third problem for a sparse but nonsymmetric matrix. To solve the model PDEs numerically we apply two space discrerization methods, namely the finite difference method and the Chebyshev collocation method. The contour integral method mentioned above is used to integrate with respect to the time variable. In the second part, we study a Hessenberg reduction method for solving shifted linear systems with a dense matrix and present numerical comparison of it with the built-in direct linear system solver in SciPy. Since both are direct methods, in the absence of roundoff errors, they give the same result. However, we find that the Hessenberg reduction method is more efficient in CPU-time than the direct solver. As application we solve a one-dimensional version of the heat equation. In the third part, we present efficient techniques for solving shifted systems with a sparse matrix by Krylov subspace methods. Because of their shift-invariance property, the Krylov methods allow one to obtain approximate solutions for all values of the parameter, by generating a single approximation space. Krylov methods applied to the linear systems are generally slowly convergent and hence preconditioning is necessary to improve the convergence. The use of shift-invert preconditioning is discussed and numerical comparisons with a direct sparse solver are presented. As an application we solve a two-dimensional version of the heat equation with and without a convection term. Our numerical experiments show that the preconditioned Krylov methods are efficient in both computational time and memory space as compared to the direct sparse solver. / AFRIKAANSE OPSOMMING: In verskeie numeriese metodes vir PDVs moet geskuifde lineêre stelsels van die vorm (zI − A)x = b, opgelos word vir verskeie waardes van die komplekse skalaar z. Hierdie stelsels is dikwels groot en yl. Hierdie tesis ondersoek numeriese metodes vir sulke stelsels wat voorkom in kontoerintegraalbenaderings vir PDVs en vergelyk hierdie metodes met direkte metodes vir oplossing. In die eerste gedeelte beskou ons drie model PDVs en bespreek numeriese benaderings om hulle op te los. Die eerste probleem word gebruik om berekenings met ’n vol matriks te demonstreer, die tweede probleem word gebruik om berekenings met yl, simmetriese matrikse te demonstreer en die derde probleem vir yl, onsimmetriese matrikse. Om die model PDVs numeries op te los beskou ons twee ruimte-diskretisasie metodes, naamlik die eindige-verskilmetode en die Chebyshev kollokasie-metode. Die kontoerintegraalmetode waarna hierbo verwys is word gebruik om met betrekking tot die tydveranderlike te integreer. In die tweede gedeelte bestudeer ons ’n Hessenberg ontbindingsmetode om geskuifde lineêre stelsels met ’n vol matriks op te los, en ons rapporteer numeriese vergelykings daarvan met die ingeboude direkte oplosser vir lineêre stelsels in SciPy. Aangesien beide metodes direk is lewer hulle dieselfde resultate in die afwesigheid van afrondingsfoute. Ons het egter bevind dat die Hessenberg ontbindingsmetode meer effektief is in terme van rekenaartyd in vergelyking met die direkte oplosser. As toepassing los ons ’n een-dimensionele weergawe van die hittevergelyking op. In die derde gedeelte beskou ons effektiewe tegnieke om geskuifde stelsels met ’n yl matriks op te los, met Krylov subruimte-metodes. As gevolg van hul skuifinvariansie eienskap, laat die Krylov metodes mens toe om benaderde oplossings te verkry vir alle waardes van die parameter, deur slegs een benaderingsruimte voort te bring. Krylov metodes toegepas op lineêre stelsels is in die algemeen stadig konvergerend, en gevolglik is prekondisionering nodig om die konvergensie te verbeter. Die gebruik van prekondisionering gebasseer op skuif-en-omkeer word bespreek en numeriese vergelykings met direkte oplossers word aangebied. As toepassing los ons ’n twee-dimensionele weergawe van die hittevergelyking op, met ’n konveksie term en daarsonder. Ons numeriese eksperimente dui aan dat die Krylov metodes met prekondisionering effektief is, beide in terme van berekeningstyd en rekenaargeheue, in vergelyking met die direkte metodes.