We present original advanced architecture implementations of the QDWHeig algo- rithm for solving dense symmetric eigenproblems. The algorithm (Y. Nakatsukasa and N. J. Higham, 2012) performs a spectral divide-and-conquer, which recursively divides the matrix into smaller submatrices by finding an invariant subspace for a subset of the spectrum. The main contribution of this thesis is to enhance the per- formance of QDWHeig algorithm by relying on a high performance kernels from PLASMA [1] and LAPACK [2]. We demonstrate the quality of the eigenpairs that are computed with the QDWHeig algorithm for many matrix types with different eigenvalue clustering. We then implement QDWHeig using kernels from LAPACK and PLASMA, and compare its performance against other divide-and-conquer sym- metric eigensolvers. The main part of QDWHeig is finding a polar decomposition. We introduce mixed precision to enhance the performance in finding the polar decom- position. Our evaluation considers speed and accuracy of the computed eigenvalues. Some applications require finding only a subspectrum of the eigenvalues; therefore we modify the algorithm to find the eigenpairs in a given interval of interest. An ex- perimental study shows significant improvement on the performance of our algorithm using mixed precision and PLASMA routines.

The variational quantum eigensolver (VQE) approach is currently one of the most promising strategies for simulating chemical systems on quantum hardware. In this work, I will describe a new quantum algorithm and a new set of classical algorithms based on VQE. The quantum algorithm, ADAPT-VQE, shows promise in mitigating many of the known limitations of VQEs: Ansatz ambiguity, local minima, and barren plateaus are all addressed to varying degrees by ADAPT-VQE. The classical algorithm family, O2DX-UCCSD, draws inspiration from VQEs, but is classically solvable in polynomial time. This group of algorithms yields equations similar to those of the linearized coupled cluster theory (LCCSD) but is more systematically improvable and, for X = 3 or X = ∞, can break single bonds, which LCCSD cannot do. The overall aim of this work is to showcase the richness of the VQE algorithm and the breadth of its derivative applications. / Doctor of Philosophy / A core goal of quantum chemistry is to compute accurate ground-state energies for molecules. Quantum computers promise to simulate quantum systems in ways that classical computers cannot. It is believed that quantum computers may be able to characterize molecules that are too large for classical computers to treat accurately. One approach to this is the variational quantum eigensolver, or VQE. The idea of a VQE is to use a quantum computer to measure the molecular energy associated with a quantum state which is parametrized by some classical set of parameters. A classical computer will use a classical optimization scheme to update those parameters before the quantum computer measures the energy again. This loop is expected to minimize the quantum resources needed for a quantum computer to be useful, since much of the work is outsourced to classical computers. In this work, I describe two novel algorithms based on the VQE which solve some of its problems.

The presence of structure in a computational problem can often be exploited and can lead to a more efficient numerical algorithm. In this dissertation, we look at structured numerical problems that arise from applications in wireless communications and machine learning that also impact other areas of scientific computing. In wireless communication system designs, certain structured matrices (frames) need to be generated. The design of such matrices is equivalent to a symmetric inverse eigenvalue problem where the values of the diagonal elements are prescribed. We present algorithms that are capable of generating a larger set of these constructions than previous algorithms. We also discuss the existence of equiangular tight frames---frames that satisfy additional structural properties. Kernel learning is an important class of problems in machine learning. It often relies on efficient numerical algorithms that solve underlying convex optimization problems. In our work, the objective functions to be minimized are the von Neumann and the LogDet Bregman matrix divergences. The algorithm that solves this optimization problem performs matrix updates based on repeated eigendecompositions of diagonal plus rank-one matrices in the case of von Neumann matrix divergence, and Cholesky updates in case of the LogDet Bregman matrix divergence. Our contribution exploits the low-rank representations and the structure of the constraint matrices, resulting in more efficient algorithms than previously known. We also present two specialized zero-finding algorithms where we exploit the structure through the shape and exact formulation of the objective function. The first zero-finding task arises during the matrix update step which is part of the above-mentioned kernel learning application. The second zero-finding problem is for the secular equation; it is equivalent to the computation of the eigenvalues of a diagonal plus rank-one matrix. The secular equation arises in various applications, the most well-known is the divide-and-conquer eigensolver. In our solutions, we build upon a somewhat forgotten zero-finding method by P. Jarratt, first described in 1966. The method employs first derivatives only and needs the same amount of evaluations as Newton's method, but converges faster. Our contributions are the more efficient specialized zero-finding algorithms. / text

The Polar Decomposition (PD) of a dense matrix is an important operation in linear algebra, while being a building block for solving the Symmetric Eigenvalue Problem (SEP) and computing the Singular Value Decomposition (SVD). It can be directly calculated through the SVD itself, or iteratively using the QR Dynamically-Weighted Halley (QDWH) algorithm. The former is difficult to parallelize due to the preponderant number of memory-bound operations during the bidiagonal reduction. The latter is an iterative method, which performs more floating-point operations than the SVD approach, but exposes at the same time more parallelism. Looking at the roadmap of the hardware technology scaling, algorithms perform- ing floating-point operations on locally cached data should be favored over those requiring expensive horizontal data movement. In this context, this thesis investigates new high-performance algorithmic designs of QDWH algorithm to compute the PD. Originally introduced by Nakatsukasa et al. [1, 2], our algorithmic contributions include mixed precision techniques, task-based formulations, and parallel asynchronous executions. Moreover, by making the PD competitive, its application to the SEP and the SVD becomes practical. In particular, we introduce for the first time new algorithms for partial SVD decomposition using QDWH. By the same token, we extend the QDWH to support partial eigen decomposition for SEP. We present new high-performance implementations of the QDWH-based algorithms relying on fine-grained computations, which allows exploiting the sparsity of the underlying data structure. To demonstrate performance efficiency, portability and scalability, we conduct benchmarking campaigns on some of the latest shared/distributed-memory systems. Our QDWH-based algorithm implementations outperform the state-of-the-art numerical libraries by up to 2.8x and 12x on shared and distributed-memory, respectively. The task-based QDWH has been integrated into the Chameleon library (https://gitlab.inria.fr/solverstack/chameleon) for support on shared-memory systems with hardware accelerators. It is also currently being used by astronomers from the Subaru telescope located at the summit of Mauna Kea, Hawaii, USA. The distributed-memory software library of QDWH and its SVD extension are freely available under modified-BSD license at https: //github.com/ecrc/qdwh.git and https://github.com/ecrc/ksvd.git, respectively. Both software libraries have been integrated into the Cray Scientific numerical library LibSci v17.11.1 and v19.02.1.

In the past two decades, myriad algorithms to elucidate the characteristics and dynamics of molecular systems have been developed for quantum computers. In this dissertation, we explore how these algorithms can be adapted to other fields, both to closely related subjects such as materials science, and more surprising subjects such as information theory. Special emphasis is placed on the Variational Quantum Eigensolver algorithm adapted to solve band structures of a periodic system; three distinct implementations are developed, each with its own advantages and disadvantages. We also see how unitary quantum circuits designed to model individual electron excitations within a molecule can be modified to prepare a quantum states strictly orthogonal to a space of known states, an important component to solve problems in thermodynamics and spectroscopy. Finally, we see how the core behavior in several quantum algorithms originally developed for quantum chemistry can be adapted to implement compressive sensing, a protocol in information theory for extrapolating large amounts of information from relatively few measurements. This body of work demonstrates that quantum algorithms developed to study molecules have immense interdisciplinary uses in fields as varied as materials science and information theory.

Este trabalho tem por finalidade desenvolver um método baseado em Otimização Topológica para projetar uma estrutura mecânica, chamada de sonotrodo, acoplada a um transdutor piezelétrico de potência (dispositivo mecânico capaz de transformar energia elétrica em deformação mecânica ou vice-versa). Um sonotrodo é uma estrutura utilizada para transmitir vibrações mecânicas de um transdutor piezelétrico, ajustando a amplitude e a distribuição dos deslocamentos gerados por essa vibração para obedecer aos requisitos do projeto do transdutor. Dentre as aplicações de transdutores piezelétricos utilizando sonotrodos, pode-se citar sonares para navegação, limpeza e solda ultrassônica, tomografia acústica, furadeiras ultrassônicas, corte ultrassônico de tecidos, etc. Os requisitos de projeto do sonotrodo variam para cada aplicação, desde a necessidade de se obter o deslocamento máximo em um único ponto do sonotrodo até a uniformização do deslocamento de um plano inteiro da estrutura. Para a obtenção do resultado ótimo, neste trabalho são aplicadas técnicas de Otimização Topológica (OT). OT é um procedimento para projetar o leiaute ótimo de estruturas distribuindo material dentro de uma região fixa. O método de OT é implementado utilizando a Programação Linear Seqüencial (PLS) como algoritmo de otimização, e é baseado na interpolação \"Simple Isotropic Material with Penalization\" (SIMP) como formulação de modelo de material. É apresentado também um estudo sobre a utilização do modelo de material \"Rational Approximation of Material Properties\" (RAMP) na tentativa de se reduzir instabilidades numéricas como modos localizados. O Método de Elementos Finitos (MEF) é aplicado para modelar o sonotrodo utilizando a formulação de elemento axissimétrico de quatro nós e de elemento em Estado Plano de Tensões Mecânicas (EPTM). É apresentada a implementação para OT estrutural contínua baseada em variáveis de projeto por nós, o que minimiza instabilidades numéricas, tais como \"instabilidade de tabuleiro\". As freqüências de ressonâncias e os modos de vibrar são computados através do método de Lanczos. É utilizado um algoritmo baseado na formulação \"Modal Assurance Criterion\" (MAC) para que um certo modo de vibrar seja encontrado, de modo que a freqüência de ressonância relacionada a esse modo seja otimizada. São apresentados exemplos para verificar a eficiência e a generalidade do método proposto, e também, um estudo sobre a influência dos parâmetros de otimização utilizadas no método. Por fim, são apresentados resultados que atendem a todos os requisitos de projeto, bem como seu pós-processamento, e análise no software comercial ANSYS®. / This work aims at the development of a method based on Topology Optimization to design a mechanical structure, called sonotrode, which is a device usually connected to a high power piezoelectric transducer (mechanical device capable of converting electric energy into mechanical displacement or vice-versa). A sonotrode transmits mechanical vibrations of a piezoelectric transducer, adjusting the amplitude and the distribution of these vibrations to fit the design needs of the transducer. Among applications of piezoelectric transducers using sonotrodes, we can cite navigation sonars, ultrasonic cleaning and melting, acoustic tomography, ultrasonic drilling, ultrasonic fabric cutting, etc. The design needs of the sonotrode differs for each application, ranging from obtaining maximum displacement in one single point of its structure, to obtaining uniform displacements on a whole face of the sonotrode. To improve the attainment of the optimum result, in this work \"Topology Optimization\" (TO) is applied to design the sonotrode. TO is a procedure to design the optimal layout of structures by distributing material within a fixed domain. The objective of the developed TO formulation is to find the best topology of the sonotrode that produces maximum and uniform displacements at one of its face. The TO method is implemented using the \"Sequential Linear Programming\" (SLP) as the optimization algorithm, and it is based on the \"Simple Isotropic Material with Penalization\" (SIMP) interpolation for material model formulation. It\'s also presented a study about the material model \"Rational Approximation of Material Properties\" (RAMP), in an attempt to reduce numerical instabilities like localized modes. \"Finite Element Method\" (FEM) is applied to model the sonotrode considering piezoelectric four-node axisymmetric elements. A node-based design variable implementation for continuum structural topology optimization is presented to minimize numerical instabilities such as \"checkerboard pattern\". The ressonance frequencies and modes are computed through Lanczos Method. A \"Modal Assurance Criterion\" (MAC) based formulation is used to track a certain mode, so that, the ressonance frequency related to this mode can be optimized. Examples are presented to verify the efficiency and the generality of the proposed method, and also, a study about the influence of the optimization parameters used in the method. Finally, results that meets all the design requirements are presented, as well as their post-processed topology, and the analysis in the commercial software ANSYS®.

How do we find patterns and anomalies, on graphs with billions of nodes and edges, which do not fit in memory? How to use parallelism for such Tera- or Peta-scale graphs? In this thesis, we propose PEGASUS, a large scale graph mining system implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. PEGASUS includes algorithms which help us spot patterns and anomalous behaviors in large graphs. PEGASUS enables the structure analysis on large graphs. We unify many different structure analysis algorithms, including the analysis on connected components, PageRank, and radius/diameter, into a general primitive called GIM-V. GIM-V is highly optimized, achieving good scale-up on the number of edges and available machines. We discover surprising patterns using GIM-V, including the 7-degrees of separation in one of the largest publicly available Web graphs, with 7 billion edges. PEGASUS also enables the inference and the spectral analysis on large graphs. We design an efficient distributed belief propagation algorithm which infer the states of unlabeled nodes given a set of labeled nodes. We also develop an eigensolver for computing top k eigenvalues and eigenvectors of the adjacency matrices of very large graphs. We use the eigensolver to discover anomalous adult advertisers in the who-follows-whom Twitter graph with 3 billion edges. In addition, we develop an efficient tensor decomposition algorithm and use it to analyze a large knowledge base tensor. Finally, PEGASUS allows the management of large graphs. We propose efficient graph storage and indexing methods to answer graph mining queries quickly. We also develop an edge layout algorithm for better compressing graphs.

Este trabalho tem por finalidade desenvolver um método baseado em Otimização Topológica para projetar uma estrutura mecânica, chamada de sonotrodo, acoplada a um transdutor piezelétrico de potência (dispositivo mecânico capaz de transformar energia elétrica em deformação mecânica ou vice-versa). Um sonotrodo é uma estrutura utilizada para transmitir vibrações mecânicas de um transdutor piezelétrico, ajustando a amplitude e a distribuição dos deslocamentos gerados por essa vibração para obedecer aos requisitos do projeto do transdutor. Dentre as aplicações de transdutores piezelétricos utilizando sonotrodos, pode-se citar sonares para navegação, limpeza e solda ultrassônica, tomografia acústica, furadeiras ultrassônicas, corte ultrassônico de tecidos, etc. Os requisitos de projeto do sonotrodo variam para cada aplicação, desde a necessidade de se obter o deslocamento máximo em um único ponto do sonotrodo até a uniformização do deslocamento de um plano inteiro da estrutura. Para a obtenção do resultado ótimo, neste trabalho são aplicadas técnicas de Otimização Topológica (OT). OT é um procedimento para projetar o leiaute ótimo de estruturas distribuindo material dentro de uma região fixa. O método de OT é implementado utilizando a Programação Linear Seqüencial (PLS) como algoritmo de otimização, e é baseado na interpolação \"Simple Isotropic Material with Penalization\" (SIMP) como formulação de modelo de material. É apresentado também um estudo sobre a utilização do modelo de material \"Rational Approximation of Material Properties\" (RAMP) na tentativa de se reduzir instabilidades numéricas como modos localizados. O Método de Elementos Finitos (MEF) é aplicado para modelar o sonotrodo utilizando a formulação de elemento axissimétrico de quatro nós e de elemento em Estado Plano de Tensões Mecânicas (EPTM). É apresentada a implementação para OT estrutural contínua baseada em variáveis de projeto por nós, o que minimiza instabilidades numéricas, tais como \"instabilidade de tabuleiro\". As freqüências de ressonâncias e os modos de vibrar são computados através do método de Lanczos. É utilizado um algoritmo baseado na formulação \"Modal Assurance Criterion\" (MAC) para que um certo modo de vibrar seja encontrado, de modo que a freqüência de ressonância relacionada a esse modo seja otimizada. São apresentados exemplos para verificar a eficiência e a generalidade do método proposto, e também, um estudo sobre a influência dos parâmetros de otimização utilizadas no método. Por fim, são apresentados resultados que atendem a todos os requisitos de projeto, bem como seu pós-processamento, e análise no software comercial ANSYS®. / This work aims at the development of a method based on Topology Optimization to design a mechanical structure, called sonotrode, which is a device usually connected to a high power piezoelectric transducer (mechanical device capable of converting electric energy into mechanical displacement or vice-versa). A sonotrode transmits mechanical vibrations of a piezoelectric transducer, adjusting the amplitude and the distribution of these vibrations to fit the design needs of the transducer. Among applications of piezoelectric transducers using sonotrodes, we can cite navigation sonars, ultrasonic cleaning and melting, acoustic tomography, ultrasonic drilling, ultrasonic fabric cutting, etc. The design needs of the sonotrode differs for each application, ranging from obtaining maximum displacement in one single point of its structure, to obtaining uniform displacements on a whole face of the sonotrode. To improve the attainment of the optimum result, in this work \"Topology Optimization\" (TO) is applied to design the sonotrode. TO is a procedure to design the optimal layout of structures by distributing material within a fixed domain. The objective of the developed TO formulation is to find the best topology of the sonotrode that produces maximum and uniform displacements at one of its face. The TO method is implemented using the \"Sequential Linear Programming\" (SLP) as the optimization algorithm, and it is based on the \"Simple Isotropic Material with Penalization\" (SIMP) interpolation for material model formulation. It\'s also presented a study about the material model \"Rational Approximation of Material Properties\" (RAMP), in an attempt to reduce numerical instabilities like localized modes. \"Finite Element Method\" (FEM) is applied to model the sonotrode considering piezoelectric four-node axisymmetric elements. A node-based design variable implementation for continuum structural topology optimization is presented to minimize numerical instabilities such as \"checkerboard pattern\". The ressonance frequencies and modes are computed through Lanczos Method. A \"Modal Assurance Criterion\" (MAC) based formulation is used to track a certain mode, so that, the ressonance frequency related to this mode can be optimized. Examples are presented to verify the efficiency and the generality of the proposed method, and also, a study about the influence of the optimization parameters used in the method. Finally, results that meets all the design requirements are presented, as well as their post-processed topology, and the analysis in the commercial software ANSYS®.

Increasing ubiquity of computational resources has enabled simulation of complex electronic systems and modern materials. The PAOFLOW software package is a tool designed to construct and analyze tight binding Hamiltonians from the solutions of DFT calculations. PAOFLOW leverages localized basis sets to greatly reduce computational costs of post-processing QE simulation results, enabling efficient determination of properties such as electronic density, band structures in the presence of electric or magnetic fields, magnetic or spin circular dichroism, spin-texture, Fermi surfaces, spin or anomalous Hall conductivity (SHC or AHC), electronic transport, and more. PAOFLOW's broad functionality is detailed in this work, and several independent studies where PAOFLOW's capabilities directly enabled research on promising candidates for ferroelectric and spintronic based technologies are described. Today, Quantum computers are at the forefront of computational information science. Materials scientists and quantum chemists can use quantum computers to simulate interacting systems of fermions, without having to perform the iterative methods of classical computing. This dissertation also describes a study where the band structure for silicon is simulated for the first time on quantum hardware and broadens this concept for simulating band structures of generic crystalline structures on quantum machines.