<p>Many kernel matrices from differential equations or data science applications possess low or approximately low off-diagonal rank for certain key matrix subblocks; such matrices are referred to as rank-structured. Operations on rank-structured matrices like factorization and linear system solution can be greatly accelerated by converting them into hierarchical matrix forms, such as the hiearchically semiseparable (HSS) matrix form. The dominant cost of this conversion process, called HSS construction, is the low-rank approximation of certain matrix blocks. Low-rank approximation is also a required step in many other contexts throughout numerical linear algebra. In this work, a proxy point low-rank approximation method is detailed for general analytic kernel matrices, in both one and several dimensions. A new accuracy analysis for this approximation is also provided, as well as numerical evidence of its accuracy. The extension of this method to kernels in several dimensions is novel, and its new accuracy analysis makes it a convenient choice to use over existing proxy point methods. Finally, a new HSS construction algorithm using this method for certain Cauchy and Toeplitz matrices is given, which is asymptotically faster than existing methods. Numerical evidence for the accuracy and efficacy of the new construction algorithm is also provided.</p>

No description available.

This thesis is concerned with the fast iterative solution of linear systems of equations of saddle point form. Saddle point problems are a ubiquitous class of matrices that arise in a host of computational science and engineering applications. The focus here is on improving the convergence of iterative methods for these problems by preconditioning. Preconditioning is a way to transform a given linear system into a different problem for which iterative methods converge faster. Saddle point matrices have a very specific block structure and many preconditioning strategies for these problems exploit this structure. The preconditioners considered in this thesis are constraint preconditioners. This class of preconditioner mimics the structure of the original saddle point problem. In this thesis, we prove norm- and field-of-values-equivalence for constraint preconditioners associated to saddle point matrices with a particular structure. As a result of these equivalences, the number of iterations needed for convergence of a constraint preconditioned minimal residual Krylov subspace method is bounded, independent of the size of the matrix. In particular, for saddle point systems that arise from the finite element discretization of partial differential equations (p.d.e.s), the number of iterations it takes for GMRES to converge for theses constraint preconditioned systems is bounded (asymptotically), independent of the size of the mesh width. Moreover, we extend these results when appropriate inexact versions of the constraint preconditioner are used. We illustrate this theory by presenting numerical experiments on saddle point matrices that arise from the finite element solution of coupled Stokes-Darcy flow. This is a system of p.d.e.s that models the coupling of a free flow to a porous media flow by conditions across the interface of the two flow regions. We present experiments in both two and three dimensions, using different types of elements (triangular, quadrilateral), different finite element schemes (continuous, discontinuous Galerkin methods), and different geometries. In all cases, the effectiveness of the constraint preconditioner is demonstrated. / Mathematics

We consider low-rank solution methods for certain classes of large-scale linear matrix equations. Our aim is to adapt existing low-rank solution methods based on standard, extended and rational Krylov subspaces to solve equations which may viewed as extensions of the classical Lyapunov and Sylvester equations. The first class of matrix equations that we consider are constrained Sylvester equations, which essentially consist of Sylvester's equation along with a constraint on the solution matrix. These therefore constitute a system of matrix equations. The second are generalized Lyapunov equations, which are Lyapunov equations with additional terms. Such equations arise as computational bottlenecks in model order reduction. / Mathematics

A graph is a mathematical structure for modelling the pairwise relations between objects. This thesis studies two types of graphs, namely, similarity-based graphs and evolving graphs. We look at ways to traverse an evolving graph. In particular, we examine the influence of temporal information on node centrality. In the process, we develop EvolvingGraphs.jl, a software package for analyzing time-dependent networks. We develop Etymo, a search system for discovering interesting research papers. Etymo utilizes both similarity-based graphs and evolving graphs to build a knowledge graph of research articles in order to help users to track the development of ideas. We construct content similarity-based graphs using the full text of research papers. And we extract key concepts from research papers and exploit the temporal information in research papers to construct a concepts evolving graph.

Application domains such as Bio-informatics, DSP, Structural Biology, Fluid Dynamics, high resolution direction finding, state estimation, adaptive noise cancellation etc. demand high performance computing solutions for their simulation environments. The core computations of these applications are in Numerical Linear Algebra (NLA) kernels. Direct solvers are predominantly required in the domains like DSP, estimation algorithms like Kalman Filter etc, where the matrices on which operations need to be performed are either small or medium sized, but dense. Faddeev's Algorithm is often used for solving dense linear system of equations. Modified Faddeev's algorithm (MFA) is a general algorithm on which LU decomposition, QR factorization or SVD of matrices can be realized. MFA has the good property of realizing a host of matrix operations by computing the Schur complements on four blocked matrices, thereby reducing the overall computation requirements. We will use MFA as a representative Direct Solver in this work. We further discuss Given's rotation based QR algorithm for Decomposition of any matrix, often used to solve the linear least square problem. Systolic Array Architectures are widely accepted ASIC solutions for NLA algorithms. But the \can of worms" associated with this traditional solution spawns the need for alternative solutions. While popular custom hardware solution in form of systolic arrays can deliver high performance, but because of their rigid structure they are not scalable and reconfigurable, and hence not commercially viable. We show how a Reconfigurable computing platform can serve to contain the \can of worms". REDEFINE, a coarse grained runtime reconfigurable architecture has been used for systolic actualization of NLA kernels. We elaborate upon streaming NLA-specific enhancements to REDEFINE in order to meet expected performance goals. We explore the need for an algorithm aware custom compilation framework. We bring about a proposition to realize Faddeev's Algorithm on REDEFINE. We show that REDEFINE performs several times faster than traditional GPPs. Further we direct our interest to QR Decomposition to be the next NLA kernel as it ensures better stability than LU and other decompositions. We use QR Decomposition as a case study to explore the design space of the proposed solution on REDEFINE. We also investigate the architectural details of the Custom Functional Units (CFU) for these NLA kernels. We determine the right size of the sub-array in accordance with the optimal pipeline depth of the core execution units and the number of such units to be used per sub-array. The framework used to realize QR Decomposition can be generalized for the realization of other algorithms dealing with decompositions like LU, Faddeev's Algorithm, Gauss-Jordon etc with different CFU definitions .

Many systems designed by electrical & computer engineers rely on electromagnetic (EM) signals to transmit, receive, and extract either information or energy. In many cases, these systems are large and complex. Their accurate, cost-effective design requires high-fidelity computer modeling of the underlying EM field/material interaction problem in order to find a design with acceptable system performance. This modeling is accomplished by projecting the governing Maxwell equations onto finite dimensional subspaces, which results in a large matrix equation representation (Zx = b) of the EM problem. In the case of integral equation-based formulations of EM problems, the M-by-N system matrix, Z, is generally dense. For this reason, when treating large problems, it is necessary to use compression methods to store and manipulate Z. One such sparse representation is provided by so-called H^2 matrices. At low-to-moderate frequencies, H^2 matrices provide a controllably accurate data-sparse representation of Z. The scale at which problems in EM are considered ``large'' is continuously being redefined to be larger. This growth of problem scale is not only happening in EM, but respectively across all other sub-fields of computational science as well. The pursuit of increasingly large problems is unwavering in all these sub-fields, and this drive has long outpaced the rate of advancements in processing and storage capabilities in computing. This has caused computational science communities to now face the computational limitations of standard linear algebraic methods that have been relied upon for decades to run quickly and efficiently on modern computing hardware. This common set of algorithms can only produce reliable results quickly and efficiently for small to mid-sized matrices that fit into the memory of the host computer. Therefore, the drive to pursue larger problems has even began to outpace the reasonable capabilities of these common numerical algorithms; the deterministic numerical linear algebra algorithms that have gotten matrix computation this far have proven to be inadequate for many problems of current interest. This has computational science communities focusing on improvements in their mathematical and software approaches in order to push further advancement. Randomized numerical linear algebra (RandNLA) is an emerging area that both academia and industry believe to be strong candidates to assist in overcoming the limitations faced when solving massive and computationally expensive problems. This thesis presents results of recent work that uses a random sampling method (RSM) to implement algebraic operations involving multiple H^2 matrices. Significantly, this work is done in a manner that is non-invasive to an existing H^2 code base for filling and factoring H^2 matrices. The work presented thus expands the existing code's capabilities with minimal impact on existing (and well-tested) applications. In addition to this work with randomized H^2 algebra, improvements in sparse factorization methods for the compressed H^2 data structure will also be presented. The reported developments in filling and factoring H^2 data structures assist in, and allow for, the further pursuit of large and complex problems in computational EM (CEM) within simulation code bases that utilize the H^2 data structure.

5章（本文31～40ページ）と元となった論文の著作権はIEEEに属するため、規約に従い、本文79ページにおいて出典を示すともに、コピーライト表記を付している。本文39、40ページの全ての図の著作権は、IEEEに属する。このため、これら全ての図においてコピーライト表記を付している。 / 京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19858号 / 情博第609号 / 新制||情||106(附属図書館) / 32894 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 中村 佳正, 教授 梅野 健, 教授 中島 浩 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

In this thesis, we develop preconditioned iterative methods for the solution of matrix systems arising from PDE-constrained optimization problems. In order to do this, we exploit saddle point theory, as this is the form of the matrix systems we wish to solve. We utilize well-known results on saddle point systems to motivate preconditioners based on effective approximations of the (1,1)-block and Schur complement of the matrices involved. These preconditioners are used in conjunction with suitable iterative solvers, which include MINRES, non-standard Conjugate Gradients, GMRES and BiCG. The solvers we use are selected based on the particular problem and preconditioning strategy employed. We consider the numerical solution of a range of PDE-constrained optimization problems, namely the distributed control, Neumann boundary control and subdomain control of Poisson's equation, convection-diffusion control, Stokes and Navier-Stokes control, the optimal control of the heat equation, and the optimal control of reaction-diffusion problems arising in chemical processes. Each of these problems has a special structure which we make use of when developing our preconditioners, and specific techniques and approximations are required for each problem. In each case, we motivate and derive our preconditioners, obtain eigenvalue bounds for the preconditioners where relevant, and demonstrate the effectiveness of our strategies through numerical experiments. The goal throughout this work is for our iterative solvers to be feasible and reliable, but also robust with respect to the parameters involved in the problems we consider.

The task of choosing a preconditioner M to use when solving a linear system Ax=b with iterative methods is often tedious and most methods remain ad-hoc. This thesis presents a randomized algorithm to make this chore less painful through use of randomized algorithms for estimating traces. In particular, we show that the preconditioner stability || I - M-1A ||F, known to forecast preconditioner quality, can be computed in the time it takes to run a constant number of iterations of conjugate gradients through use of sketching methods. This is in spite of folklore which suggests the quantity is impractical to compute, and a proof we give that ensures the quantity could not possibly be approximated in a useful amount of time by a deterministic algorithm. Using our estimator, we provide a method which can provably select a quality preconditioner among n candidates using floating operations commensurate with running about n log(n) steps of the conjugate gradients algorithm. In the absence of such a preconditioner among the candidates, our method can advise the practitioner to use no preconditioner at all. The algorithm is extremely easy to implement and trivially parallelizable, and along the way we provide theoretical improvements to the literature on trace estimation. In empirical experiments, we show the selection method can be quite helpful. For example, it allows us to create to the best of our knowledge the first preconditioning method for kernel regression which never uses more iterations over the non-preconditioned analog in standard settings.