This dissertation describes a theoretical study of strongly correlated electron systems. We present a variational quantum Monte Carlo approach based on matrix-product states, which enables us to naturally extend our work into higher-dimensional tensor-network states as well as to determine the ground state and the low-lying excitations of quasi-onedimensional electron systems. Our results show that the ground state of the quarterilled zigzag electron ladder is expected to exhibit a bond distortion whose pattern is not affected by the electron-electron interaction strength. This dissertation also presents a new method that combines a quantumMonte Carlo technique with a class of tensor-network states. We show that this method can be applied to two-dimensional fermionic or frustrated models that suffer from a sign problem. Monte Carlo sampling over physical states reveals better scaling with the size of matrices under periodic boundary conditions than other types of higher-dimensional tensor-network states, such as projected entangled-pair states, which lead to unfavorable exponential scaling in the matrix size.

The spin structure factor is the dynamical information coming from inelastic neutron scattering. In this work we develop the technology of tensor networks as a numerical tool to be able to compute physical observables reliably for one-dimensional quantum systems. The main technical message of this thesis is that tensor networks provide a controlled way to compute spin structure factors. The algorithms in this thesis are tested on the anisotropic Majumdar--Ghosh model and the results of these simulations are presented and discussed. / Thesis / Master of Science (MSc)

We study the totally asymmetric exclusion process on the positive integers with a single particle source at the origin. Liggett (1975) has shown that the long term behaviour of this process has a phase transition: If the particle production rate at the source and the initial density are below certain critical values, the stationary measure is a product measure, otherwise the stationary measure is spatially correlated. Following the approach of Derrida et al. (1993) it was shown by Grosskinsky (2004) that these correlations can be described by means of a matrix product representation. In this thesis we derive a large deviation principle with explicit rate function for the particle density in a macroscopic box based on this representation. The novel and rigorous technique we develop for this problem combines spectral theoretical and combinatorial ideas and has the potential to be applicable to other models described by matrix products.

No description available.

Avec l’émergence du calcul haute-performance (HPC) et des applications Big Data, de nouvelles problématiques cruciales sont apparues. Parmi elles on trouve le problème du transfert de données, c’est-à-dire des communications entre machines, qui peut génerer des délais lors de gros calculs en plus d’avoir un impact sur la consommation énergétique. La réplication, que ce soit de tâches ou de fichiers, est un facteur qui accroît ces communications, tout en étant un outil quasi-indispensable pour améliorer le parallélisme du calcul et la résistance aux pannes. Dans cette thèse nous nous intéressons à la réplication de fichiers et à son impact sur les communications au travers de deux problèmes. Dans le premier, la multiplication de matrices en parallèle, le but est de limiter autant que possible ces réplications pour diminuer la quantité de données déplacées. Dans le second, l’ordonnancement de la phase « Map » de MapReduce, il existe une réplication initiale qu’il faut utiliser au mieux afin d’obtenir l’ordonnancement le plus rapide ou entraînant le moins de création de nouvelles copies. En plus de la réplication, nous nous intéressons aussi à la comparaison entre stratégies d’ordonnancement statiques (allocations faites en amont du calcul) et dynamiques (allocations faites pendant le calcul) sur ces deux problèmes avec pour objectif de créer des stratégies hybrides mélangeant les deux aspects. Pour le premier problème, le produit de matrices en parallèle, nous nous ramenons à un problème de partition de carré où l’équilibrage de charge est donné en entrée. Cet équilibrage donné, le but est de minimiser la somme des semi-paramètres des rectangles couvrant des zones ainsi créés. Ce problème a déjà été étudié par le passé et nous démontrons de nouveaux résultats. Nous proposons ainsi deux nouveaux algorithmes d’approximation, l’un fondé sur une stratégie récursive et l’autre sur l’usage d’une courbe fractale. Nous présentons également une modélisation alternative, fondée sur un problème similaire de partition de cube, dont nous prouvons la NP-complétude tout en fournissant deux algorithmes d’approximation. Pour finir, nous réalisons également une implémentation pratique du produit de matrices en utilisant nos stratégies d’allocation grâce à la librairie StarPU. Les résultats expérimentaux montrent une amélioration du temps de calcul ainsi qu’une diminution significative des transferts de données lorsqu’on utilise une stratégie statique d’allocation couplée à une technique de vol de tâches. Pour le second problème, l’ordonnancement de la phase « Map » de MapReduce, plusieurs copies des fichiers d’entrée sont distribuées parmi les processeurs disponibles. Le but ici est de faire en sorte que chaque tâche soit attribuée à un processeur possédant son fichier d’entrée tout en ayant le meilleur temps de calcul total. Une autre option étudiée est d’autoriser les tâches nonlocales (attribués à des processeurs ne possédant pas leurs fichiers d’entrée) mais d’en limiter le nombre. Dans cette thèse nous montrons premièrement qu’un algorithme glouton pour ce problème peut être modélisé par un processus de « balls-in-bins » avec choix, impliquant une surcharge (nombre de tâches supplémentaires par rapport à la moyenne) en O(mlogm) où m est le nombre de processeurs. Secondement, dans le cas où les tâches non-locales sont interdites, nous relions le problème à celui de l’orientation de graphes, ce qui permet d’obtenir des algorithmes optimaux et polynomiaux et l’existence d’une assignation presque parfaite avec forte probabilité. Dans le cas où les tâches non locales sont autorisées, nous proposons également des algorithmes polynomiaux et optimaux. Finalement, nous proposons un ensemble de simulations pour montrer l’efficacité de nos méthodes dans le cas de tâches faiblement hétérogènes. / The increasing importance of High Performance Computing (HPC) and Big Data applications creates new issues in parallel computing. One of them is communication, the data transferred from a processor to another. Such data movements have an impact on computational time, inducing delays and increase of energy consumption. If replication, of either tasks or files, generates communication, it is also an important tool to improve resiliency and parallelism. In this thesis, we focus on the impact of the replication of input files on the overall amount of communication. For this purpose, we concentrate on two practical problems. The first one is parallel matrix multiplication. In this problem, the goal is to induce as few replications as possible in order to decrease the amount of communication. The second problem is the scheduling of the “Map” phase in the MapReduce framework. In this case, replication is an input of the problem and this time the goal is to use it in the best possible way. In addition to the replication issue, this thesis also considers the comparison between static and dynamic approaches for scheduling. For consistency, static approaches compute schedules before starting the computation while dynamic approaches compute the schedules during the computation itself. In this thesis we design hybrid strategies in order to take advantage of the pros of both. First, we relate communication-avoiding matrix multiplication with a square partitioning problem, where load-balancing is given as an input. In this problem, the goal is to split a square into zones (whose areas depend on the relative speed of resources) while minimizing the sum of their half-perimeters. We improve the existing results in the literature for this problem with two additional approximation algorithms. In addition we also propose an alternative model using a cube partitioning problem. We prove the NP-completeness of the associated decision problem and we design two approximations algorithms. Finally, we implement the algorithms for both problems in order to provide a comparison of the schedules for matrix multiplication. For this purpose, we rely on the StarPU library. Second, in the Map phase of MapReduce scheduling case, the input files are replicated and distributed among the processors. For this problem we propose two metrics. In the first one, we forbid non-local tasks (a task that is processed on a processor that does not own its input files) and under this constraint, we aim at minimizing the makespan. In the second problem, we allow non-local tasks and we aim at minimizing them while minimizing makespan. For the theoretical study, we focus on tasks with homogeneous computation times. First, we relate a greedy algorithm on the makespan metric with a “ball-into-bins” process, proving that this algorithm produces solutions with expected overhead (the difference between the number of tasks on the most loaded processor and the number of tasks in a perfect distribution) equal to O(mlogm) where m denotes the number of processors. Second, we relate this scheduling problem (with forbidden non-local tasks) to a problem of graph orientation and therefore prove, with the results from the literature, that there exists, with high probability, a near-perfect assignment (whose overhead is at most 1). In addition, there are polynomial-time optimal algorithms. For the communication metric case, we provide new algorithms based on a graph model close to matching problems in bipartite graphs. We prove that these algorithms are optimal for both communication and makespan metrics. Finally, we provide simulations based on traces from a MapReduce cluster to test our strategies with realistic settings and prove that the algorithms we propose perform very well in the case of low or medium variance of the computation times of the different tasks of a job.

This thesis is divided into two parts, each part exploring a different topic within the general area of nonlinear algebra. In the first part, we study several applications of tensors. First, we study tensor networks, and more specifically: uniform matrix product states. We use methods from nonlinear algebra and algebraic geometry to answer questions about topology, defining equations, and identifiability of uniform matrix product states. By an interplay of theorems from algebra, geometry, and quantum physics we answer several questions and conjectures posed by Critch, Morton and Hackbusch. In addition, we prove a tensor version of the so-called quantum Wielandt inequality, solving an open problem regarding the higher-dimensional version of matrix product states. Second, we present new contributions to the study of fast matrix multiplication. Motivated by the symmetric version of matrix multiplication we study the plethysm S^k(sl_n) of the adjoint representation sl_n of the Lie group SL_n . Moreover, we discuss two algebraic approaches for constructing new tensors which could potentially be used to prove new upper bounds on the complexity of matrix multiplication. One approach is based on the highest weight vectors of the aforementioned plethysm. The other approach uses smoothable finite-dimensional algebras. Finally, we study the Hessian discriminant of a cubic surface, a recently introduced invariant defined in terms of the Waring rank. We express the Hessian discriminant in terms of fundamental invariants. This answers Question 15 of the 27 questions on the cubic surface posed by Bernd Sturmfels. In the second part of this thesis, we apply algebro-geometric methods to study matroids and flag matroids. We review a geometric interpretation of the Tutte polynomial in terms of the equivariant K-theory of the Grassmannian. By generalizing Grassmannians to partial flag varieties, we obtain a new invariant of flag matroids: the flag-geometric Tutte polynomial. We study this invariant in detail, and prove several interesting combinatorial properties.

This master's thesis is focused on analysis of EVONA a.s. product range, which is manufacturing company. Aim of this study is to analyze the range of underwear, thermal underwear and hosiery and then to propose optimization measures. The theoretical part is devoted to methods which focus on analyzing the marketing environment and product mix. In the practical part, internal company data of EVONA a.s. served to analyze the product range by using Boston Consulting Group matrix and General Electric Business matrix. To illustrate the situation a survey was carried out and it helped in the final recommendations of the product range.

Designing efficient code in practice for a given computation is a hard task. In this thesis, we tackle this issue in two different situations. The first part of the thesis introduces some algorithmic improvements in structured linear algebra. We first show how to extend an algorithm by Cardinal for inverting Cauchy-like matrices to the other common structures. This approach, which mainly relies on products of the type "structured matrix × matrix", leads to a theoretical speed-up of a factor up to 7 that we also observe in practice. Then, we extend some works on Toeplitz-like matrices and prove that, for any of the common structures, the product of an n×n structured matrix of displacement rank α by an n×α matrix can be computed in Õ(α^(ω-1)n). This leads to direct inversion algorithms in Õ(α^(ω-1)n) , that do not rely on a reduction to the Toeplitz-like case. The second part of the thesis deals with the implementation of arithmetic expressions. This topic raises several issues like finding the minimum number of operations, and maximizing the speed or the accuracy when using some finite-precision arithmetic. Making use of the inductive nature of arithmetic expressions enables the design of algorithms that help to answer such questions. We thus present a set of algorithms for generating evaluation schemes, counting them, and optimizing them according to one or several criteria. These algorithms are part of a library that we have developed and used, among other things, in order to decrease the running time of a code generator for a mathematical library, and to study optimality issues about the evaluation of a small degree polynomial with scalar coefficients at a matrix point.

No description available.

Quantum computers have the potential to solve certain problems in minutes that would otherwise take classical computers thousands of years due to the exponential speed-up certain quantum algorithms have over classical algorithms. In order to leverage such quantum algorithms, it is necessary for them to run on quantum devices. Examples of such devices include, but are not limited to, semiconductor and superconducting qubits, and semiconductor single and entangled photon emitters. The conventional method of constructing a semiconductor qubit is to apply gates on a semiconductor surface to localize electrons, where the electronic spin states are mapped to a qubit basis. Examples of this include the spin qubit where the spin-1/2 states of a single electron is the qubit basis and the gated singlet-triplet qubit where the states of two coupled electrons are mapped to a qubit basis. In general, gated semiconductor spin qubits are subject to decoherence from the environment which alters the electronic wavefunction by entanglement with the nuclear spins and phonons in the lattice compromising the stability of the qubit. Semiconductor nanostructures can also be designed as photon emitters. Self-assembled quantum dots are an example of such nanostructures and have been shown to emit single photons through exciton recombination and entangled photons through biexciton-exciton cascade. The difficulty in designing photon sources using self-assembled quantum dots is that the size and shape varies from dot to dot, implying that the electronic and magnetic properties also vary. In this thesis, I present the design of a single photon emitter using an InAsP quantum dot embedded in an InP nanowire and the design of a singlet-triplet qubit that is topologically protected from decoherence using an array of such quantum dots embedded in an InP nanowire. The advantage of using quantum dot nanowires over self-assembled quantum dots as photon emitters is that the quantum dot thickness, radius and composition can be controlled deterministically using a technique known as vapour-liquid-solid epitaxy which allows the emission spectrum to be engineered. Using a microscopic model, I simulated an InAsP quantum dot embedded in a nanowire with upwards of millions of atoms and showed that the emission spectrum came in agreement with the actual InAsP/InP quantum dot nanowires that were fabricated at the National Research Council of Canada. Moreover, I showed that altering the distribution of As atoms in the quantum dot can cause dramatic change in the emission spectrum. For the design of the topologically protected singlet-triplet qubit, I demonstrated that the ground state of an array of such quantum dots embedded in an InP nanowire, with four electrons in each dot, is four-fold degenerate and is topologically protected from higher energy states, making the ground state robust against perturbations. This state is known as the Haldane phase and can be understood in terms of two spin-1/2 quasiparticles at each edge of the array. Though the spectral gap in my simulation was of the order of 1 meV, this work provides insight into the potential design of a room temperature operating Haldane qubit where the spectral gap is of the order of room temperature.