To see the other types of publications on this topic, follow the link: Algebras, Linear Algorithms.
Dissertations / Theses on the topic 'Algebras, Linear Algorithms'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Algebras, Linear Algorithms.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Gunnels, John Andrew. "A systematic approach to the design and analysis of linear algebra algorithms." Access restricted to users with UT Austin EID Full text (PDF) from UMI/Dissertation Abstracts International, 2001. http://wwwlib.umi.com/cr/utexas/fullcit?p3037015.
Full text
2
Porter, Annabelle Louise. "The evolution of equation-solving: Linear, quadratic, and cubic." CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/3069.
Full textAbstract:
This paper is intended as a professional developmental tool to help secondary algebra teachers understand the concepts underlying the algorithms we use, how these algorithms developed, and why they work. It uses a historical perspective to highlight many of the concepts underlying modern equation solving.
3
Wu, Wenhao. "High-performance matrix multiplication hierarchical data structures, optimized kernel routines, and qualitative performance modeling /." Master's thesis, Mississippi State : Mississippi State University, 2003. http://library.msstate.edu/etd/show.asp?etd=etd-07092003-003633.
Full text
4
Rocha, Eugénio Alexandre Miguel. "Uma Abordagem Algébrica à Teoria de Controlo Não Linear." Doctoral thesis, Universidade de Aveiro, 2003. http://hdl.handle.net/10773/21444.
Full textAbstract:
Doutoramento em MatemáticaNesta tese de Doutoramento desenvolve-se principalmente uma abordagem algébrica à teoria de sistemas de controlo não lineares. No entanto, outros tópicos são também estudados. Os tópicos tratados são os seguidamente enunciados: fórmulas para sistemas de controlo sobre álgebras de Lie livres, estabilidade de um sistema de corpos rolantes, algoritmos para aritmética digital, e equações integrais de Fredholm não lineares. No primeiro e principal tópico estudam-se representações para as soluções de sistemas de controlo lineares no controlo. As suas trajetórias são representadas pelas chamadas séries de Chen. Estuda-se a representação formal destas séries através da introdução de várias álgebras não associativas e técnicas específicas de álgebras de Lie livres. Sistemas de coordenadas para estes sistemas são estudados, nomeadamente, coordenadas de primeiro tipo e de segundo tipo. Apresenta-se uma demonstração alternativa para as coordenadas de segundo tipo e obtêm-se expressões explícitas para as coordenadas de primeiro tipo. Estas últimas estão intimamente ligadas ao logaritmo da série de Chen que, por sua vez, tem fortes relações com uma fórmula designada na literatura por “continuous Baker-Campbell- Hausdorff formula”. São ainda apresentadas aplicações à teoria de funções simétricas não comutativas. É, por fim, caracterizado o mapa de monodromia de um campo de vectores não linear e periódico no tempo em relação a uma truncatura do logaritmo de Chen. No segundo tópico é estudada a estabilizabilidade de um sistema de quaisquer dois corpos que rolem um sobre o outro sem deslizar ou torcer. Constroem-se controlos fechados e dependentes do tempo que tornam a origem do sistema de dois corpos num sistema localmente assimptoticamente estável. Vários exemplos e algumas implementações em Maple°c são discutidos. No terceiro tópico, em apêndice, constroem-se algoritmos para calcular o valor de várias funções fundamentais na aritmética digital, sendo possível a sua implementação em microprocessadores. São também obtidos os seus domínios de convergência. No último tópico, também em apêndice, demonstra-se a existência e unicidade de solução para uma classe de equações integrais não lineares com atraso. O atraso tem um carácter funcional, mostrando-se ainda a diferenciabilidade no sentido de Fréchet da solução em relação à função de atraso.
In this PhD thesis several subjects are studied regarding the following topics: formulas for nonlinear control systems on free Lie algebras, stabilizability of nonlinear control systems, digital arithmetic algorithms, and nonlinear Fredholm integral equations with delay. The first and principal topic is mainly related with a problem known as the continuous Baker-Campbell-Hausdorff exponents. We propose a calculus to deal with formal nonautonomous ordinary differential equations evolving on the algebra of formal series defined on an alphabet. We introduce and connect several (non)associative algebras as Lie, shuffle, zinbiel, pre-zinbiel, chronological (pre-Lie), pre-chronological, dendriform, D-I, and I-D. Most of those notions were also introduced into the universal enveloping algebra of a free Lie algebra. We study Chen series and iterated integrals by relating them with nonlinear control systems linear in control. At the heart of all the theory of Chen series resides a zinbiel and shuffle homomorphism that allows us to construct a purely formal representation of Chen series on algebras of words. It is also given a pre-zinbiel representation of the chronological exponential, introduced by A.Agrachev and R.Gamkrelidze on the context of a tool to deal with nonlinear nonautonomous ordinary differential equations over a manifold, the so-called chronological calculus. An extensive description of that calculus is made, collecting some fragmented results on several publications. It is a fundamental tool of study along the thesis. We also present an alternative demonstration of the result of H.Sussmann about coordinates of second kind using the mentioned tools. This simple and comprehensive proof shows that coordinates of second kind are exactly the image of elements of the dual basis of a Hall basis, under the above discussed homomorphism. We obtain explicit expressions for the logarithm of Chen series and the respective coordinates of first kind, by defining several operations on a forest of leaf-labelled trees. It is the same as saying that we have an explicit formula for the functional coefficients of the Lie brackets on a continuous Baker-Campbell-Hausdorff-Dynkin formula when a Hall basis is used. We apply those formulas to relate some noncommutative symmetric functions, and we also connect the monodromy map of a time-periodic nonlinear vector field with a truncation of the Chen logarithm. On the second topic, we study any system of two bodies rolling one over the other without twisting or slipping. By using the Chen logarithm expressions, the monodromy map of a flow and Lyapunov functions, we construct time-variant controls that turn the origin of a control system linear in control into a locally asymptotically stable equilibrium point. Stabilizers for control systems whose vector fields generate a nilpotent Lie algebra with degree of nilpotency · 3 are also given. Some examples are presented and Maple°c were implemented. The third topic, on appendix, concerns the construction of efficient algorithms for Digital Arithmetic, potentially for the implementation in microprocessors. The algorithms are intended for the computation of several functions as the division, square root, sines, cosines, exponential, logarithm, etc. By using redundant number representations and methods of Lyapunov stability for discrete dynamical systems, we obtain several algorithms (that can be glued together into an algorithm for parallel execution) having the same core and selection scheme in each iteration. We also prove their domains of convergence and discuss possible extensions. The last topic, also on appendix, studies the set of solutions of a class of nonlinear Fredholm integral equations with general delay. The delay is of functional character modelled by a continuous lag function. We ensure existence and uniqueness of a continuous (positive) solution of such equation. Moreover, under additional conditions, it is obtained the Fr´echet differentiability of the solution with respect to the lag function.
5
Yelkenci, Serhat. "Algorithmic Music Composition Using Linear Algebra." Thesis, Southern Illinois University at Edwardsville, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10275073.
Full textAbstract:
Sound, in its all forms, is a source of energy whose capabilities humankind is not yet fully aware of. Composition - the way of aggregating sounds into the form of music - still holds to be an unperceived methodology with lots of unknowns. Methodologies used by composers are generally seem as being innate talent, something that cannot be used or shared by others. Yet, as any other form of art, music actually is and can be interpreted with mathematics and geometry. The focus of this thesis is to propose a generative algorithm to compose structured music pieces using linear algebra as the mathematical language for the representation of music. By implementing the linear algebra as the scientific framework, a practical data structure is obtained for analysis and manipulation. Instead of defining a single structure from a certain musical canon, which is a type of limiting the frame of music, the generative algorithm proposed in this paper is capable of learning all kinds of musical structures by linear algebra operations. The algorithm is designed to build musical knowledge (influence) by analyzing music pieces and receive a new melody as the inspirational component to produce new unique and meaningful music pieces. Characteristic analysis features obtained from analyzing music pieces, serves as constraints during the composition process. The proposed algorithm has been successful in generating unique and meaningful music pieces. The process time of the algorithm varies due to complexity of the influential aspect. Yet, the free nature of the generative algorithm and the capability of matrical representation offer a practical linkage between unique and meaningful music creation and any other concept containing a mathematical foundation.
6
Delaplace, Claire. "Algorithmes d'algèbre linéaire pour la cryptographie." Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S045/document.
Full textAbstract:
Dans cette thèse, nous discutons d’aspects algorithmiques de trois différents problèmes, en lien avec la cryptographie. La première partie est consacrée à l’algèbre linéaire creuse. Nous y présentons un nouvel algorithme de pivot de Gauss pour matrices creuses à coefficients exacts, ainsi qu’une nouvelle heuristique de sélection de pivots, qui rend l’entière procédure particulièrement efficace dans certains cas. La deuxième partie porte sur une variante du problème des anniversaires, avec trois listes. Ce problème, que nous appelons problème 3XOR, consiste intuitivement à trouver trois chaînes de caractères uniformément aléatoires de longueur fixée, telles que leur XOR soit la chaîne nulle. Nous discutons des considérations pratiques qui émanent de ce problème et proposons un nouvel algorithme plus rapide à la fois en théorie et en pratique que les précédents. La troisième partie est en lien avec le problème learning with errors (LWE). Ce problème est connu pour être l’un des principaux problèmes difficiles sur lesquels repose la cryptographie à base de réseaux euclidiens. Nous introduisons d’abord un générateur pseudo-aléatoire, basé sur la variante dé-randomisée learning with rounding de LWE, dont le temps d’évaluation est comparable avec celui d’AES. Dans un second temps, nous présentons une variante de LWE sur l’anneau des entiers. Nous montrerons que dans ce cas le problème est facile à résoudre et nous proposons une application intéressante en re-visitant une attaque par canaux auxiliaires contre le schéma de signature BLISSIn this thesis, we discuss algorithmic aspects of three different problems, related to cryptography. The first part is devoted to sparse linear algebra. We present a new Gaussian elimination algorithm for sparse matrices whose coefficients are exact, along with a new pivots selection heuristic, which make the whole procedure particularly efficient in some cases. The second part treats with a variant of the Birthday Problem with three lists. This problem, which we call 3XOR problem, intuitively consists in finding three uniformly random bit-strings of fixed length, such that their XOR is the zero string. We discuss practical considerations arising from this problem, and propose a new algorithm which is faster in theory as well as in practice than previous ones. The third part is related to the learning with errors (LWE) problem. This problem is known for being one of the main hard problems on which lattice-based cryptography relies. We first introduce a pseudorandom generator, based on the de-randomised learning with rounding variant of LWE, whose running time is competitive with AES. Second, we present a variant of LWE over the ring of integers. We show that in this case the problem is easier to solve, and we propose an interesting application, revisiting a side-channel attack against the BLISS signature scheme
7
Weihrauch, Christian. "Analysis of Monte Carlo algorithms for linear algebra problems." Thesis, University of Reading, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.515747.
Full text
8
Iakymchuk, Roman [Verfasser]. "Performance modeling and prediction for linear algebra algorithms / Roman Iakymchuk." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2012. http://d-nb.info/1026308690/34.
Full text
9
Sato, Hiroyuki. "Riemannian Optimization Algorithms and Their Applications to Numerical Linear Algebra." 京都大学 (Kyoto University), 2013. http://hdl.handle.net/2433/180615.
Full text
10
Maust, Reid S. "Optimal power flow using a genetic algorithm and linear algebra." Morgantown, W. Va. : [West Virginia University Libraries], 1999. http://etd.wvu.edu/templates/showETD.cfm?recnum=1163.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 1999.Title from document title page. Document formatted into pages; contains vi, 91 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 41-42).
11
Kannan, Ramaseshan. "Numerical linear algebra problems in structural analysis." Thesis, University of Manchester, 2014. https://www.research.manchester.ac.uk/portal/en/theses/numerical-linear-algebra-problems-in-structural-analysis(7df0f708-fc12-4807-a1f5-215960d9c4d4).html.
Full textAbstract:
A range of numerical linear algebra problems that arise in finite element-based structural analysis are considered. These problems were encountered when implementing the finite element method in the software package Oasys GSA. We present novel solutions to these problems in the form of a new method for error detection, algorithms with superior numerical effeciency and algorithms with scalable performance on parallel computers. The solutions and their corresponding software implementations have been integrated into GSA's program code and we present results that demonstrate the use of these implementations by engineers to solve real-world structural analysis problems.
12
Kaya, Dogan. "Parallel algorithms for numerical linear algebra on a shared memory multiprocessor." Thesis, University of Newcastle Upon Tyne, 1995. http://hdl.handle.net/10443/2008.
Full textAbstract:
This thesis discusses a variety of parallel algorithms for linear algebra problems including the solution of the linear system of equations Ax = b using QR and L U decomposition, reduction of a general matrix A to Hessenberg form, reduction of a real symmetric matrix B to tridiagonal form, and solution of the symmetric tridiagonal eigenproblem. Empirical comparisons are carried out using various different versions of the above algorithms and this is described in this thesis. We also compare three different synchronisation mechanisms when applied to the reduction to Hessenberg form problem. We implement Cuppen's method for computing both eigenvalues and eigenvectors of a real symmetric tridiagonal matrix T using both recursive and non-recursive implementations. We consider parallel implementations of these versions and also consider parallelisation of the matrix multiplication part of the algorithm. We present some numerical results illustrating an experimental evaluation of the effect of deflation on accuracy, comparison of the parallel implementations and comparison of the additional parallelisation for matrix multiplication. 11 A variety of algorithms are investigated which involve varying amounts of overlap between different parts of the calculation and collecting together updates as far as possible to make good use of the storage hierarchy of the shared memory multiprocessor. Algorithms using dynamic task allocation are compared with ones which do not. The results presented have been obtained using the C++ programming language, with parallel constructs provided by the Encore Parallel Threads package on a shared memory Encore Multimax (MIMD) computer. The experimental results demonstrate that dynamic task allocation can be sometimes very effective on this machine, and that very high efficiency is often obtainable with careful construction of the parallel algorithms even for relatively small matrices.
13
Lamas, Daviña Alejandro. "Dense and sparse parallel linear algebra algorithms on graphics processing units." Doctoral thesis, Universitat Politècnica de València, 2018. http://hdl.handle.net/10251/112425.
Full textAbstract:
Una línea de desarrollo seguida en el campo de la supercomputación es el uso de procesadores de propósito específico para acelerar determinados tipos de cálculo. En esta tesis estudiamos el uso de tarjetas gráficas como aceleradores de la computación y lo aplicamos al ámbito del álgebra lineal. En particular trabajamos con la biblioteca SLEPc para resolver problemas de cálculo de autovalores en matrices de gran dimensión, y para aplicar funciones de matrices en los cálculos de aplicaciones científicas. SLEPc es una biblioteca paralela que se basa en el estándar MPI y está desarrollada con la premisa de ser escalable, esto es, de permitir resolver problemas más grandes al aumentar las unidades de procesado.
El problema lineal de autovalores, Ax = lambda x en su forma estándar, lo abordamos con el uso de técnicas iterativas, en concreto con métodos de Krylov, con los que calculamos una pequeña porción del espectro de autovalores. Este tipo de algoritmos se basa en generar un subespacio de tamaño reducido (m) en el que proyectar el problema de gran dimensión (n), siendo m << n. Una vez se ha proyectado el problema, se resuelve este mediante métodos directos, que nos proporcionan aproximaciones a los autovalores del problema inicial que queríamos resolver. Las operaciones que se utilizan en la expansión del subespacio varían en función de si los autovalores deseados están en el exterior o en el interior del espectro. En caso de buscar autovalores en el exterior del espectro, la expansión se hace mediante multiplicaciones matriz-vector. Esta operación la realizamos en la GPU, bien mediante el uso de bibliotecas o mediante la creación de funciones que aprovechan la estructura de la matriz. En caso de autovalores en el interior del espectro, la expansión requiere resolver sistemas de ecuaciones lineales. En esta tesis implementamos varios algoritmos para la resolución de sistemas de ecuaciones lineales para el caso específico de matrices con estructura tridiagonal a bloques, que se ejecutan en GPU.
En el cálculo de las funciones de matrices hemos de diferenciar entre la aplicación directa de una función sobre una matriz, f(A), y la aplicación de la acción de una función de matriz sobre un vector, f(A)b. El primer caso implica un cálculo denso que limita el tamaño del problema. El segundo permite trabajar con matrices dispersas grandes, y para resolverlo también hacemos uso de métodos de Krylov. La expansión del subespacio se hace mediante multiplicaciones matriz-vector, y hacemos uso de GPUs de la misma forma que al resolver autovalores. En este caso el problema proyectado comienza siendo de tamaño m, pero se incrementa en m en cada reinicio del método. La resolución del problema proyectado se hace aplicando una función de matriz de forma directa. Nosotros hemos implementado varios algoritmos para calcular las funciones de matrices raíz cuadrada y exponencial, en las que el uso de GPUs permite acelerar el cálculo.One line of development followed in the field of supercomputing is the use of specific purpose processors to speed up certain types of computations. In this thesis we study the use of graphics processing units as computer accelerators and apply it to the field of linear algebra. In particular, we work with the SLEPc library to solve large scale eigenvalue problems, and to apply matrix functions in scientific applications. SLEPc is a parallel library based on the MPI standard and is developed with the premise of being scalable, i.e. to allow solving larger problems by increasing the processing units. We address the linear eigenvalue problem, Ax = lambda x in its standard form, using iterative techniques, in particular with Krylov's methods, with which we calculate a small portion of the eigenvalue spectrum. This type of algorithms is based on generating a subspace of reduced size (m) in which to project the large dimension problem (n), being m << n. Once the problem has been projected, it is solved by direct methods, which provide us with approximations of the eigenvalues of the initial problem we wanted to solve. The operations used in the expansion of the subspace vary depending on whether the desired eigenvalues are from the exterior or from the interior of the spectrum. In the case of searching for exterior eigenvalues, the expansion is done by matrix-vector multiplications. We do this on the GPU, either by using libraries or by creating functions that take advantage of the structure of the matrix. In the case of eigenvalues from the interior of the spectrum, the expansion requires solving linear systems of equations. In this thesis we implemented several algorithms to solve linear systems of equations for the specific case of matrices with a block-tridiagonal structure, that are run on GPU. In the computation of matrix functions we have to distinguish between the direct application of a matrix function, f(A), and the action of a matrix function on a vector, f(A)b. The first case involves a dense computation that limits the size of the problem. The second allows us to work with large sparse matrices, and to solve it we also make use of Krylov's methods. The expansion of subspace is done by matrix-vector multiplication, and we use GPUs in the same way as when solving eigenvalues. In this case the projected problem starts being of size m, but it is increased by m on each restart of the method. The solution of the projected problem is done by directly applying a matrix function. We have implemented several algorithms to compute the square root and the exponential matrix functions, in which the use of GPUs allows us to speed up the computation.
Una línia de desenvolupament seguida en el camp de la supercomputació és l'ús de processadors de propòsit específic per a accelerar determinats tipus de càlcul. En aquesta tesi estudiem l'ús de targetes gràfiques com a acceleradors de la computació i ho apliquem a l'àmbit de l'àlgebra lineal. En particular treballem amb la biblioteca SLEPc per a resoldre problemes de càlcul d'autovalors en matrius de gran dimensió, i per a aplicar funcions de matrius en els càlculs d'aplicacions científiques. SLEPc és una biblioteca paral·lela que es basa en l'estàndard MPI i està desenvolupada amb la premissa de ser escalable, açò és, de permetre resoldre problemes més grans en augmentar les unitats de processament. El problema lineal d'autovalors, Ax = lambda x en la seua forma estàndard, ho abordem amb l'ús de tècniques iteratives, en concret amb mètodes de Krylov, amb els quals calculem una xicoteta porció de l'espectre d'autovalors. Aquest tipus d'algorismes es basa a generar un subespai de grandària reduïda (m) en el qual projectar el problema de gran dimensió (n), sent m << n. Una vegada s'ha projectat el problema, es resol aquest mitjançant mètodes directes, que ens proporcionen aproximacions als autovalors del problema inicial que volíem resoldre. Les operacions que s'utilitzen en l'expansió del subespai varien en funció de si els autovalors desitjats estan en l'exterior o a l'interior de l'espectre. En cas de cercar autovalors en l'exterior de l'espectre, l'expansió es fa mitjançant multiplicacions matriu-vector. Aquesta operació la realitzem en la GPU, bé mitjançant l'ús de biblioteques o mitjançant la creació de funcions que aprofiten l'estructura de la matriu. En cas d'autovalors a l'interior de l'espectre, l'expansió requereix resoldre sistemes d'equacions lineals. En aquesta tesi implementem diversos algorismes per a la resolució de sistemes d'equacions lineals per al cas específic de matrius amb estructura tridiagonal a blocs, que s'executen en GPU. En el càlcul de les funcions de matrius hem de diferenciar entre l'aplicació directa d'una funció sobre una matriu, f(A), i l'aplicació de l'acció d'una funció de matriu sobre un vector, f(A)b. El primer cas implica un càlcul dens que limita la grandària del problema. El segon permet treballar amb matrius disperses grans, i per a resoldre-ho també fem ús de mètodes de Krylov. L'expansió del subespai es fa mitjançant multiplicacions matriu-vector, i fem ús de GPUs de la mateixa forma que en resoldre autovalors. En aquest cas el problema projectat comença sent de grandària m, però s'incrementa en m en cada reinici del mètode. La resolució del problema projectat es fa aplicant una funció de matriu de forma directa. Nosaltres hem implementat diversos algorismes per a calcular les funcions de matrius arrel quadrada i exponencial, en les quals l'ús de GPUs permet accelerar el càlcul.
Lamas Daviña, A. (2018). Dense and sparse parallel linear algebra algorithms on graphics processing units [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/112425
TESIS
14
Feng, Wei Pate Thomas H. "The QR algorithm for eigenvalue estimation theory and experiments /." Auburn, Ala, 2008. http://hdl.handle.net/10415/1488.
Full text
15
Nguyen, Hong Diep. "Efficient algorithms for verified scientific computing : Numerical linear algebra using interval arithmetic." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00680352.
Full textAbstract:
Interval arithmetic is a means to compute verified results. However, a naive use of interval arithmetic does not provide accurate enclosures of the exact results. Moreover, interval arithmetic computations can be time-consuming. We propose several accurate algorithms and efficient implementations in verified linear algebra using interval arithmetic. Two fundamental problems are addressed, namely the multiplication of interval matrices and the verification of a floating-point solution of a linear system. For the first problem, we propose two algorithms which offer new tradeoffs between speed and accuracy. For the second problem, which is the verification of the solution of a linear system, our main contributions are twofold. First, we introduce a relaxation technique, which reduces drastically the execution time of the algorithm. Second, we propose to use extended precision for few, well-chosen parts of the computations, to gain accuracy without losing much in term of execution time.
16
Musco, Cameron N. (Cameron Nicholas). "The power of randomized algorithms : from numerical linear algebra to biological systems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120424.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 323-347).
In this thesis we study simple, randomized algorithms from a dual perspective. The first part of the work considers how randomized methods can be used to accelerate the solution of core problems in numerical linear algebra. In particular, we give a randomized low-rank approximation algorithm for positive semidefinite matrices that runs in sublinear time, significantly improving upon what is possible with traditional deterministic methods. We also discuss lower bounds on low-rank approximation and spectral summarization problems that attempt to explain the importance of randomization and approximation in accelerating linear algebraic computation. The second part of the work considers how the theory of randomized algorithms can be used more generally as a tool to understand how complexity emerges from low-level stochastic behavior in biological systems. We study population density- estimation in ant colonies, which is a key primitive in social decision-making and task allocation. We define a basic computational model and show how agents in this model can estimate their density using a simple random-walk-based algorithm. We also consider simple randomized algorithms for computational primitives in spiking neural networks, focusing on fast winner-take-all networks.
by Cameron Nicholas Musco.
Ph. D.
17
Fabregat, Traver Diego [Verfasser]. "Knowledge-based automatic generation of linear algebra algorithms and code / Diego Fabregat Traver." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2014. http://d-nb.info/1052303080/34.
Full text
18
Gomes, Neto Francisco de Assis Magalhães 1964. "Minimização de funções quadraticas com algeba linear adaptativa e aplicações." [s.n.], 1995. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307441.
Full textAbstract:
Orientador: Jose Mario MartinezTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica
Made available in DSpace on 2018-07-20T05:24:48Z (GMT). No. of bitstreams: 1 GomesNeto_FranciscodeAssisMagalhaes_D.pdf: 2662734 bytes, checksum: bab718dc42406f664ee7a530da9a333c (MD5) Previous issue date: 1995
Resumo: Não informado.
Abstract: Not informed.
Doutorado
Doutor em Matemática Aplicada
19
Zounon, Mawussi. "On numerical resilience in linear algebra." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0038/document.
Full textAbstract:
Comme la puissance de calcul des systèmes de calcul haute performance continue de croître, en utilisant un grand nombre de cœurs CPU ou d’unités de calcul spécialisées, les applications hautes performances destinées à la résolution des problèmes de très grande échelle sont de plus en plus sujettes à des pannes. En conséquence, la communauté de calcul haute performance a proposé de nombreuses contributions pour concevoir des applications tolérantes aux pannes. Cette étude porte sur une nouvelle classe d’algorithmes numériques de tolérance aux pannes au niveau de l’application qui ne nécessite pas de ressources supplémentaires, à savoir, des unités de calcul ou du temps de calcul additionnel, en l’absence de pannes. En supposant qu’un mécanisme distinct assure la détection des pannes, nous proposons des algorithmes numériques pour extraire des informations pertinentes à partir des données disponibles après une pannes. Après l’extraction de données, les données critiques manquantes sont régénérées grâce à des stratégies d’interpolation pour constituer des informations pertinentes pour redémarrer numériquement l’algorithme. Nous avons conçu ces méthodes appelées techniques d’Interpolation-restart pour des problèmes d’algèbre linéaire numérique tels que la résolution de systèmes linéaires ou des problèmes aux valeurs propres qui sont indispensables dans de nombreux noyaux scientifiques et applications d’ingénierie. La résolution de ces problèmes est souvent la partie dominante; en termes de temps de calcul, des applications scientifiques. Dans le cadre solveurs linéaires du sous-espace de Krylov, les entrées perdues de l’itération sont interpolées en utilisant les entrées disponibles sur les nœuds encore disponibles pour définir une nouvelle estimation de la solution initiale avant de redémarrer la méthode de Krylov. En particulier, nous considérons deux politiques d’interpolation qui préservent les propriétés numériques clés de solveurs linéaires bien connus, à savoir la décroissance monotone de la norme-A de l’erreur du gradient conjugué ou la décroissance monotone de la norme résiduelle de GMRES. Nous avons évalué l’impact du taux de pannes et l’impact de la quantité de données perdues sur la robustesse des stratégies de résilience conçues. Les expériences ont montré que nos stratégies numériques sont robustes même en présence de grandes fréquences de pannes, et de perte de grand volume de données. Dans le but de concevoir des solveurs résilients de résolution de problèmes aux valeurs propres, nous avons modifié les stratégies d’interpolation conçues pour les systèmes linéaires. Nous avons revisité les méthodes itératives de l’état de l’art pour la résolution des problèmes de valeurs propres creux à la lumière des stratégies d’Interpolation-restart. Pour chaque méthode considérée, nous avons adapté les stratégies d’Interpolation-restart pour régénérer autant d’informations spectrale que possible. Afin d’évaluer la performance de nos stratégies numériques, nous avons considéré un solveur parallèle hybride (direct/itérative) pleinement fonctionnel nommé MaPHyS pour la résolution des systèmes linéaires creux, et nous proposons des solutions numériques pour concevoir une version tolérante aux pannes du solveur. Le solveur étant hybride, nous nous concentrons dans cette étude sur l’étape de résolution itérative, qui est souvent l’étape dominante dans la pratique. Les solutions numériques proposées comportent deux volets. A chaque fois que cela est possible, nous exploitons la redondance de données entre les processus du solveur pour effectuer une régénération exacte des données en faisant des copies astucieuses dans les processus. D’autre part, les données perdues qui ne sont plus disponibles sur aucun processus sont régénérées grâce à un mécanisme d’interpolationAs the computational power of high performance computing (HPC) systems continues to increase by using huge number of cores or specialized processing units, HPC applications are increasingly prone to faults. This study covers a new class of numerical fault tolerance algorithms at application level that does not require extra resources, i.e., computational unit or computing time, when no fault occurs. Assuming that a separate mechanism ensures fault detection, we propose numerical algorithms to extract relevant information from available data after a fault. After data extraction, well chosen part of missing data is regenerated through interpolation strategies to constitute meaningful inputs to numerically restart the algorithm. We have designed these methods called Interpolation-restart techniques for numerical linear algebra problems such as the solution of linear systems or eigen-problems that are the inner most numerical kernels in many scientific and engineering applications and also often ones of the most time consuming parts. In the framework of Krylov subspace linear solvers the lost entries of the iterate are interpolated using the available entries on the still alive nodes to define a new initial guess before restarting the Krylov method. In particular, we consider two interpolation policies that preserve key numerical properties of well-known linear solvers, namely the monotony decrease of the A-norm of the error of the conjugate gradient or the residual norm decrease of GMRES. We assess the impact of the fault rate and the amount of lost data on the robustness of the resulting linear solvers.For eigensolvers, we revisited state-of-the-art methods for solving large sparse eigenvalue problems namely the Arnoldi methods, subspace iteration methods and the Jacobi-Davidson method, in the light of Interpolation-restart strategies. For each considered eigensolver, we adapted the Interpolation-restart strategies to regenerate as much spectral information as possible. Through intensive experiments, we illustrate the qualitative numerical behavior of the resulting schemes when the number of faults and the amount of lost data are varied; and we demonstrate that they exhibit a numerical robustness close to that of fault-free calculations. In order to assess the efficiency of our numerical strategies, we have consideredan actual fully-featured parallel sparse hybrid (direct/iterative) linear solver, MaPHyS, and we proposed numerical remedies to design a resilient version of the solver. The solver being hybrid, we focus in this study on the iterative solution step, which is often the dominant step in practice. The numerical remedies we propose are twofold. Whenever possible, we exploit the natural data redundancy between processes from the solver toperform an exact recovery through clever copies over processes. Otherwise, data that has been lost and is not available anymore on any process is recovered through Interpolationrestart strategies. These numerical remedies have been implemented in the MaPHyS parallel solver so that we can assess their efficiency on a large number of processing units (up to 12; 288 CPU cores) for solving large-scale real-life problems
20
Brenčys, Liutauras. "Puasono lygties sprendimas naudojantis šaltinio apibendrintomis hiperbolinės funkcijomis." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2011. http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2011~D_20110804_100133-71588.
Full textAbstract:
Sudarytas Puasono lygties sprendimo per „rutuliukų“ potencialus algoritmas. Šiuo metodu Puasono lygties sprendimo uždavinys suvedamas į tiesinių algebrinių lygčių sistemos sprendimą. Sudaryta ir išbandyta matematiniu paketu MATHCAD to sprendimo programa. Palyginti gauti sprendiniai su tais, kurie gaunami analiziškai, įvertintas gautų sprendinių tikslumas. Šį sprendimo būdą galima panaudoti realiems fizikiniams potencialams paskaičiuoti, turint galvoje realų potencialą su kuriuo realūs krūviai.It consists of Poisson equation solution in the "ball" potential algorithm. In this method the Poisson equation, the decision problem are reduced to linear algebraic equations system solution. Created and tested a mathematical package MATHCAD program for that decision. Compared to solutions with those obtained analytically, estimated to obtain accurate solutions. This solution can be used to calculate the real physical potentials, given the real potential of the real workloads.
21
Barbieri, Caroline Domingues Porto do Nascimento [UNESP]. "Aperfeiçoamento do método clause-column table para a geração eficiente de implicantes primos." Universidade Estadual Paulista (UNESP), 2014. http://hdl.handle.net/11449/126338.
Full textAbstract:
Made available in DSpace on 2015-08-20T17:09:32Z (GMT). No. of bitstreams: 0
Previous issue date: 2014-11-11. Added 1 bitstream(s) on 2015-08-20T17:26:54Z : No. of bitstreams: 1
000846221.pdf: 1635996 bytes, checksum: 3433248530a7bdc61a9bdbec1086772b (MD5)A geração eficiente de implicantes primos é um fator importante na fase de cobertura dos mintermos em métodos de minimização de funções booleanas. Este trabalho apresenta uma versão aprimorada do método denominado de Clause-Column Table, utilizado na geração de implicantes primos. Neste novo algoritmo adicionou-se o teorema da adjacência e um novo critério de parada. Estas modificações evitaram a geração de termos nulos e iterações desnecessárias que ocorriam no algoritmo original. O algoritmo original e o aprimorado foram implementados em linguagem C e comparados. O método Clause-Column Table Aprimorado também foi comparado com o método Quine-McCluskey e Expander. Os resultados comprovaram que a versão aprimorada gera menos iterações que a versão original, e que na maioria das funções analisadas evitou-se a geração de termos nulos. Ao comparar com o método de Quine-McCluskey e o Expander comprovou-se que o método Clause-Column Table Aprimorado é superior na geração dos implicantes primos, pois em alguns casos elimina aqueles que não são necessários para a cobertura da função. De posse dos implicantes primos o problema de cobertura dos mintermos foi formulado como um problema de programação linear inteira 0 e 1, em que a solução se abre a todos os avanços ocorridos na área de programação linear visando a obtenção de uma solução mínima
Efficient generation of prime implicants is an important factor in the coverage phase of minterms in minimization's methods of Boolean functions. This research presents an improved version of the method called Clause-Column Table, used to generate prime implicants. In this new algorithm was added to the adjacency theorem and a new stopping criterion. These modifications prevented the generation of null terms and unnecessary iterations that occurred in the original algorithm. The original and improved algorithms were implemented in C language and compared. The Clause-Column Table Improved method was compared with the Expander and Quine-McCluskey method. The results proved that the improved version generates fewer iterations than the original version, and that in most functions analyzed it was avoided the generation of null terms. Comparing Quine-McCluskey method and the Expander it was proved that the Clause-Column Table Enhanced method is superior in the generation of prime implicants, since in some cases eliminates those who are not required to cover the function. In ownership of the prime implicants the cover problem of minterms was formulated as an integer linear programming problem of 0 and 1, where the solution is open to all advances in the area of linear programming in order to obtain a minimal solution
22
Kochinke, Sebastian. "Special Linear Systems on Curves and Algorithmic Applications." Doctoral thesis, Universitätsbibliothek Leipzig, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-219598.
Full textAbstract:
Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar.
In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden.
Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts.
Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten.
Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet.
23
Turnes, Christopher Kowalczyk. "Efficient solutions to Toeplitz-structured linear systems for signal processing." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/51878.
Full textAbstract:
This research develops efficient solution methods for linear systems with scalar and multi-level Toeplitz structure. Toeplitz systems are common in one-dimensional signal-processing applications, and typically correspond to temporal- or spatial-invariance in the underlying physical phenomenon. Over time, a number of algorithms have been developed to solve these systems economically by exploiting their structure. These developments began with the Levinson-Durbin recursion, a classical fast method for solving Toeplitz systems that has become a standard algorithm in signal processing. Over time, more advanced routines known as superfast algorithms were introduced that are capable of solving Toeplitz systems with even lower asymptotic complexity. For multi-dimensional signals, temporally- and spatially-invariant systems have linear-algebraic descriptions characterized by multi-level Toeplitz matrices, which exhibit Toeplitz structure on multiple levels. These matrices lack the same algebraic properties and structural simplicity of their scalar analogs. As a result, it has proven exceedingly difficult to extend the existing scalar Toeplitz algorithms for their treatment. This research presents algorithms to solve scalar and two-level Toeplitz systems through a constructive approach, using methods devised for specialized cases to build more general solution methods. These methods extend known scalar Toeplitz inversion results to more general scalar least-squares problems and to multi-level Toeplitz problems. The resulting algorithms have the potential to provide substantial computational gains for a large class of problems in signal processing, such as image deconvolution, non-uniform resampling, and the reconstruction of spatial volumes from non-uniform Fourier samples.
24
Peh, Lawrence T. W. "An efficient algorithm for extracting Boolean functions from linear threshold gates, and a synthetic decompositional approach to extracting Boolean functions from feedforward neural networks with arbitrary transfer functions." University of Western Australia. Dept. of Computer Science, 2000. http://theses.library.uwa.edu.au/adt-WU2003.0013.
Full textAbstract:
[Formulae and special characters can only be approximated here. Please see the pdf version of the Abstract for an accurate reproduction.] Artificial neural networks are universal function approximators that represent functions subsymbolically by weights, thresholds and network topology. Naturally, the representation remains the same regardless of the problem domain. Suppose a network is applied to a symbolic domain. It is difficult for a human to dynamically construct the symbolic function from the neural representation. It is also difficult to retrain networks on perturbed training vectors, to resume training with different training sets, to form a new neuron by combining trained neurons, and to reason with trained neurons. Even the original training set does not provide a symbolic representation of the function implemented by the trained network because the set may be incomplete or inconsistent, and the training phase may terminate with residual errors. The symbolic information in the network would be more useful if it is available in the language of the problem domain. Algorithms that translate the subsymbolic neural representation to a symbolic representation are called extraction algorithms. I argue that extraction algorithms that operate on single-output, layered feedforward networks are sufficient to analyse the class of multiple-output networks with arbitrary connections, including recurrent networks. The translucency dimensions of the ADT taxonomy for feedforward networks classifies extraction approaches as pedagogical, eclectic, or decompositional. Pedagogical and eclectic approaches typically use a symbolic learning algorithm that takes the network’s input-output behaviour as its raw data. Both approaches construct a set of input patterns and observe the network’s output for each pattern. Eclectic and pedagogical approaches construct the input patterns respectively with and without reference to the network’s internal information. These approaches are suitable for approximating the network’s function using a probably-approximately-correct (PAC) or similar framework, but they are unsuitable for constructing the network’s complete function. Decompositional approaches use internal information from a network more directly to produce the network’s function in symbolic form. Decompositional algorithms have two components. The first component is a core extraction algorithm that operates on a single neuron that is assumed to implement a symbolic function. The second component provides the superstructure for the first. It consists of a decomposition rule for producing such neurons and a recomposition rule for symbolically aggregating the extracted functions into the symbolic function of the network. This thesis makes contributions to both components for Boolean extraction. I introduce a relatively efficient core algorithm called WSX based on a novel Boolean form called BvF. The algorithm has a worst case complexity of O(2 to power of n divided by the square root of n) for a neuron with n inputs, but in all cases, its complexity can also be expressed as O(l) with an O(n) precalculation phase, where l is the length of the extracted expression in terms of the number of symbols it contains. I extend WSX for approximate extraction (AWSX) by introducing an interval about the neuron’s threshold. Assuming that the input patterns far from the threshold are more symbolically significant to the neuron than those near the threshold, ASWX ignores the neuron’s mappings for the symbolically input patterns, remapping them as convenient for efficiency. In experiments, this dramatically decreased extraction time while retaining most of the neuron’s mappings for the training set. Synthetic decomposition is this thesis’ contribution to the second component of decompositional extraction. Classical decomposition decomposes the network into its constituent neurons. By extracting symbolic functions from these neurons, classical decomposition assumes that the neurons implement symbolic functions, or that approximating the subsymbolic computation in the neurons with symbolic computation does not significantly affect the network’s symbolic function. I show experimentally that this assumption does not always hold. Instead of decomposing a network into its constituent neurons, synthetic decomposition uses constraints in the network that have the same functional form as neurons that implement Boolean functions; these neurons are called synthetic neurons. I present a starting point for constructing synthetic decompositional algorithms, and proceed to construct two such algorithms, each with a different strategy for decomposition and recomposition. One of the algorithms, ACX, works for networks with arbitrary monotonic transfer functions, so long as an inverse exists for the functions. It also has an elegant geometric interpretation that leads to meaningful approximations. I also show that ACX can be extended to layered networks with any number of layers.
25
Fasi, Massimiliano. "Weighted geometric mean of large-scale matrices: numerical analysis and algorithms." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/8274/.
Full textAbstract:
Computing the weighted geometric mean of large sparse matrices is an operation that tends to become rapidly intractable, when the size of the matrices involved grows. However, if we are not interested in the computation of the matrix function itself, but just in that of its product times a vector, the problem turns simpler and there is a chance to solve it even when the matrix mean would actually be impossible to compute. Our interest is motivated by the fact that this calculation has some practical applications, related to the preconditioning of some operators
arising in domain decomposition of elliptic problems.
In this thesis, we explore how such a computation can be efficiently performed. First, we exploit the properties of the weighted geometric mean and find several equivalent ways to express it through real powers of a matrix. Hence, we focus
our attention on matrix powers and examine how well-known techniques can be adapted to the solution of the problem at hand. In particular, we consider two broad families of approaches for the computation of f(A) v, namely quadrature
formulae and Krylov subspace methods, and generalize them to the pencil case f(A\B) v.
Finally, we provide an extensive experimental evaluation of the proposed algorithms and also try to assess how convergence speed and execution time are influenced by some characteristics of the input matrices. Our results suggest that a few elements have some bearing on the performance and that, although there is no best choice in general, knowing the conditioning and the sparsity of the arguments beforehand can considerably help in choosing the best strategy to tackle the problem.
26
Srđan, Milićević. "Algorithms for computing the optimal Geršgorin-type localizations." Phd thesis, Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, 2020. https://www.cris.uns.ac.rs/record.jsf?recordId=114425&source=NDLTD&language=en.
Full textAbstract:
There are numerous ways to localize eigenvalues. One of the best known results is that the spectrum of a given matrix ACn,n is a subset of a union of discs centered at diagonal elements whose radii equal to the sum of the absolute values of the off-diagonal elements of a corresponding row in the matrix. This result (Geršgorin's theorem, 1931) is one of the most important and elegant ways of eigenvalues localization ([63]). Among all Geršgorintype sets, the minimal Geršgorin set gives the sharpest and the most precise localization of the spectrum ([39]). In this thesis, new algorithms for computing an efficient and accurate approximation of the minimal Geršgorin set are presented.Постоје бројни начини за локализацију карактеристичних корена. Један од најчувенијих резултата је да се спектар дате матрице АCn,n налази у скупу који представља унију кругова са центрима у дијагоналним елементима матрице и полупречницима који су једнаки суми модула вандијагоналних елемената одговарајуће врсте у матрици. Овај резултат (Гершгоринова теорема, 1931.), сматра се једним од најзначајнијих и најелегантнијих начина за локализацију карактеристичних корена ([61]). Међу свим локализацијама Гершгориновог типа, минимални Гершгоринов скуп даје најпрецизнију локализацију спектра ([39]). У овој дисертацији, приказани су нови алгоритми за одређивање тачне и поуздане апроксимације минималног Гершгориновог скупа.
Postoje brojni načini za lokalizaciju karakterističnih korena. Jedan od najčuvenijih rezultata je da se spektar date matrice ACn,n nalazi u skupu koji predstavlja uniju krugova sa centrima u dijagonalnim elementima matrice i poluprečnicima koji su jednaki sumi modula vandijagonalnih elemenata odgovarajuće vrste u matrici. Ovaj rezultat (Geršgorinova teorema, 1931.), smatra se jednim od najznačajnijih i najelegantnijih načina za lokalizaciju karakterističnih korena ([61]). Među svim lokalizacijama Geršgorinovog tipa, minimalni Geršgorinov skup daje najprecizniju lokalizaciju spektra ([39]). U ovoj disertaciji, prikazani su novi algoritmi za određivanje tačne i pouzdane aproksimacije minimalnog Geršgorinovog skupa.
27
Moreau, Gilles. "On the Solution Phase of Direct Methods for Sparse Linear Systems with Multiple Sparse Right-hand Sides." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN084/document.
Full textAbstract:
Cette thèse se concentre sur la résolution de systèmes linéaires creux dans le contexte d’applications massivement parallèles. Ce type de problèmes s’exprime sous la forme AX=B, où A est une matrice creuse d’ordre n x n, i.e. qui possède un nombre d’entrées nulles suffisamment élevé pour pouvoir être exploité, et B et X sont respectivement la matrice de seconds membres et la matrice de solution de taille n x nrhs. Cette résolution par des méthodes dites directes est effectuée grâce à une étape de factorisation qui réduit A en deux matrices triangulaires inférieure et supérieure L et U, suivie de deux résolutions triangulaires pour calculer la solution.Nous nous intéressons à ces résolutions avec une attention particulière apportée à la première, LY=B. Dans beaucoup d’applications, B possède un grand nombre de colonnes (nrhs >> 1) transformant la phase de résolution en un goulot d’étranglement. Elle possède souvent aussi une structure creuse, donnant l’opportunité de réduire la complexité de cette étape.Cette étude aborde sous des angles complémentaires la résolution triangulaire de systèmes linéaires avec seconds membres multiples et creux. Nous étudions dans un premier temps la complexité asymptotique de cette étape dans différents contextes (2D, 3D, facteurs compressés ou non). Nous considérons ensuite l’exploitation de cette structure et présentons de nouvelles approches s’appuyant sur une modélisation du problème par des graphes qui permettent d’atteindre efficacement le nombre minimal d’opérations. Enfin, nous donnons une interprétation concrète de son exploitation sur une application d’électromagnétisme pour la géophysique. Nous adaptons aussi des algorithmes parallèles aux spécificités de la phase de résolution.Nous concluons en combinant l'ensemble des résultats précédents et en discutant des perspectives de ce travailWe consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives
28
Cabarcas, Daniel. "Gröbner Bases Computation and Mutant Polynomials." University of Cincinnati / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1307321300.
Full text
29
Åkerling, Erik, and Jimmy Jerenfelt. "Analys och framtagning av algoritm för rodermätning." Thesis, Örebro universitet, Institutionen för naturvetenskap och teknik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:oru:diva-23459.
Full textAbstract:
Arbetet är ett utredningsarbete som går ut på att försöka lokalisera felkällor och göra förbättringar på en testutrustning som mäter rodervinklar på akterdelen på en robot. Rapporten innehåller en översiktlig bild över den tidigare metoden och dess felkällor som hittas vid test av den tidigare metoden. Utredningen utmanar också många utav antagandena som är gjorda för beräkningarna av den tidigare metoden. Detta utförs för att kunna bekräfta eller dementera antagandena. Detta görs i form av matematiska modeller som testar olika delar av metoden. Varje del i rapporten består av en beskrivning av vad kapitlet avser följt av felkällorna som upptäckts i metoden när den testas i modellen. Det framtagna metodförslaget utsätts samma prövning som den tidigare metoden för att utreda skillnaderna. I resultatet kan man se de slutsatser som dragit av varje del av utförandet.The task is an investigation to try and locate errors and make improvements on a test equipment that measures rudder angles on the rear-end of a robot. The report contains an overview of the previous method and the errors that is found by testing it. The investigation also challenges many of the assumptions made when the previous method was made. This was made in order to either confirm or deny the assumptions. This is done by the use of mathematical models to simulate different parts of the method. Each part of the report consists of a description of the section followed by explaining the discovered errors that was found by testing the method in the models. The new produced method suggestion is exposed to the same tests as the previous method to discern the differences. The conclusions made from the sections can be found in the results.
30
Maddah, Sumayya Suzy. "Formal reduction of differential systems : Singularly-perturbed linear differential systems and completely integrable Pfaffian systems with normal crossings." Thesis, Limoges, 2015. http://www.theses.fr/2015LIMO0065/document.
Full textAbstract:
Dans cette thèse, nous nous sommes intéressés à l'analyse locale de systèmes différentiels linéaires singulièrement perturbés et de systèmes de Pfaff complètement intégrables et multivariés à croisements normaux. De tels systèmes ont une vaste littérature et se retrouvent dans de nombreuses applications. Cependant, leur résolution symbolique est toujours à l'étude. Nos approches reposent sur l'état de l'art de la réduction formelle des systèmes linéaires singuliers d'équations différentielles ordinaires univariées (ODS). Dans le cas des systèmes différentiels linéaires singulièrement perturbés, les complications surviennent essentiellement à cause du phénomène des points tournants. Nous généralisons les notions et les algorithmes introduits pour le traitement des ODS afin de construire des solutions formelles. Les algorithmes sous-jacents sont également autonomes (par exemple la réduction de rang, la classification de la singularité, le calcul de l'indice de restriction). Dans le cas des systèmes de Pfaff, les complications proviennent de l'interdépendance des multiples sous-systèmes et de leur nature multivariée. Néanmoins, nous montrons que les invariants formels de ces systèmes peuvent être récupérés à partir d'un ODS associé, ce qui limite donc le calcul à des corps univariés. De plus, nous donnons un algorithme de réduction de rang et nous discutons des obstacles rencontrés. Outre ces deux systèmes, nous parlons des singularités apparentes des systèmes différentiels univariés dont les coefficients sont des fonctions rationnelles et du problème des valeurs propres perturbées. Les techniques développées au sein de cette thèse facilitent les généralisations d'autres algorithmes disponibles pour les systèmes différentiels univariés aux cas des systèmes bivariés ou multivariés, et aussi aux systèmes d''equations fonctionnellesIn this thesis, we are interested in the local analysis of singularly-perturbed linear differential systems and completely integrable Pfaffian systems in several variables. Such systems have a vast literature and arise profoundly in applications. However, their symbolic resolution is still open to investigation. Our approaches rely on the state of art of formal reduction of singular linear systems of ordinary differential equations (ODS) over univariate fields. In the case of singularly-perturbed linear differential systems, the complications arise mainly from the phenomenon of turning points. We extend notions introduced for the treatment of ODS to such systems and generalize corresponding algorithms to construct formal solutions in a neighborhood of a singularity. The underlying components of the formal reduction proposed are stand-alone algorithms as well and serve different purposes (e.g. rank reduction, classification of singularities, computing restraining index). In the case of Pfaffian systems, the complications arise from the interdependence of the multiple components which constitute the former and the multivariate nature of the field within which reduction occurs. However, we show that the formal invariants of such systems can be retrieved from an associated ODS, which limits computations to univariate fields. Furthermore, we complement our work with a rank reduction algorithm and discuss the obstacles encountered. The techniques developed herein paves the way for further generalizations of algorithms available for univariate differential systems to bivariate and multivariate ones, for different types of systems of functional equations
31
Sharify, Meisam. "Algorithmes de mise à l'échelle et méthodes tropicales en analyse numérique matricielle." Phd thesis, Ecole Polytechnique X, 2011. http://pastel.archives-ouvertes.fr/pastel-00643836.
Full textAbstract:
L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée.
32
DiPaolo, Conner. "Randomized Algorithms for Preconditioner Selection with Applications to Kernel Regression." Scholarship @ Claremont, 2019. https://scholarship.claremont.edu/hmc_theses/230.
Full textAbstract:
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.
33
Jacquelin, Mathias. "Memory-aware algorithms : from multicores to large scale platforms." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00662525.
Full textAbstract:
This thesis focus on memory-aware algorithms tailored for hierarchical memory architectures, found for instance within multicore processors. We first study the matrix product on multicore architectures. We model such a processor, and derive lower bounds on the communication volume. We introduce three ad hoc algorithms, and experimentally assess their performance.We then target a more complex operation: the QR factorization of tall matrices. We revisit existing algorithms to better exploit the parallelism of multicore processors. We thus study the critical paths of many algorithms, prove some of them to be asymptotically optimal, and assess their performance.In the next study, we focus on scheduling streaming applications onto a heterogeneous multicore platform, the QS 22. We introduce a model of the platform and use steady-state scheduling techniques so as to maximize the throughput. We present a mixed integer programming approach that computes an optimal solution, and propose simpler heuristics. We then focus on minimizing the amount of required memory for tree-shaped workflows, and target a classical two-level memory system. I/O represent transfers from a memory to the other. We propose a new exact algorithm, and show that there exist trees where postorder traversals are arbitrarily bad. We then study the problem of minimizing the I/O volume for a given memory, show that it is NP-hard, and provide a set of heuristics.Finally, we compare archival policies for BLUE WATERS. We introduce two archival policies and adapt the well known RAIT strategy. We provide a model of the tape storage platform, and use it to assess the performance of the three policies through simulation.
34
Farabegoli, Bruno. "Analisi delle componenti principali." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amslaurea.unibo.it/11479/.
Full textAbstract:
La tesi descrive il metodo dell'analisi delle componenti principali, vertendo sia sull'aspetto matematico che la caratterizza sia su alcune sue applicazioni. Vengono anche definite le nozioni di algebra lineare e statistica fondamentali per la sua descrizione.
35
Bacha, Inès. "Traitement symbolique des systèmes d'équations différentielles non linéaires au voisinage des singularités." Université Joseph Fourier (Grenoble), 1997. http://www.theses.fr/1997GRE10078.
Full textAbstract:
Cette these se rattache a l'etude locale des equations differentielles, elle est composee de trois parties dependantes. Dans la premiere partie, nous presentons differentes theories telles que les formes normales, les transformations quasi-monomiales ainsi que celle du polygone de newton afin de mettre en place un algorithme pour simplifier les systemes planaires d'equations differentielles au voisinage des singularites isolees. Cet algorithme se base essentiellement sur les travaux d'a. Bruno sur les solutions locales des systemes d'equations differentielles. Quelques exemples d'application sont donnes afin d'illustrer ce travail. Dans la deuxieme partie, les differentes theories precedentes ainsi que l'etude des courbes algebriques nous permettent d'etendre cet algorithme dans l'espace. Dans la partie finale, nous proposons une methode de reduction de l'ordre des systemes differentiels en dimension n.
36
Asafu-Adjei, Joseph Kwaku. "Probabilistic Methods." VCU Scholars Compass, 2007. http://hdl.handle.net/10156/1420.
Full text
37
Ishigami, Hiroyuki. "Studies on Parallel Solvers Based on Bisection and Inverse Iterationfor Subsets of Eigenpairs and Singular Triplets." 京都大学 (Kyoto University), 2016. http://hdl.handle.net/2433/215685.
Full textAbstract:
5章（本文31～40ページ）と元となった論文の著作権はIEEEに属するため、規約に従い、本文79ページにおいて出典を示すともに、コピーライト表記を付している。本文39、40ページの全ての図の著作権は、IEEEに属する。このため、これら全ての図においてコピーライト表記を付している。Kyoto University (京都大学)
0048
新制・課程博士
博士(情報学)
甲第19858号
情博第609号
新制||情||106(附属図書館)
32894
京都大学大学院情報学研究科数理工学専攻
(主査)教授 中村 佳正, 教授 梅野 健, 教授 中島 浩
学位規則第4条第1項該当
38
Pecatte, Timothée. "Bornes inférieures et algorithmes de reconstruction pour des sommes de puissances affines." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN029/document.
Full textAbstract:
Le cadre général de cette thèse est l'étude des polynômes comme objets de modèles de calcul. Cette approche permet de définir de manière précise la complexité d'évaluation d'un polynôme, puis de classifier des familles de polynômes en fonction de leur difficulté dans ce modèle. Dans cette thèse, nous nous intéressons en particulier au modèle AffPow des sommes de puissance de forme linéaire, i.e. les polynômes qui s'écrivent $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, avec $\deg \ell_i = 1$. Ce modèle semble assez naturel car il étend à la fois le modèle de Waring $f = \sum \alpha_i \ell_i^d$ et le modèle du décalage creux $f = \sum \alpha_i \ell^{e_i}$, mais peu de résultats sont connus pour cette généralisation.Nous avons pu prouver des résultats structurels pour la version univarié de ce modèle, qui nous ont ensuite permis d'obtenir des bornes inférieures et des algorithmes de reconstruction, qui répondent au problème suivant : étant donné $f = \sum \alpha_i (x-a_i)^{e_i}$ par la liste de ses coefficients, retrouver les $\alpha_i, a_i, e_i$ qui apparaissent dans la décomposition optimale de $f$.Nous avons aussi étudié plus en détails la version multivarié du modèle, qui avait été laissé ouverte par nos précédents algorithmes de reconstruction, et avons obtenu plusieurs résultats lorsque le nombre de termes dans une expression optimale est relativement petit devant le nombre de variables ou devant le degré du polynômeThe general framework of this thesis is the study of polynomials as objects of models of computation. This approach allows to define precisely the evaluation complexity of a polynomial, and then to classify families of polynomials depending on their complexity. In this thesis, we focus on the study of the model of sums of affine powers, that is polynomials that can be written as $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, with $\deg \ell_i = 1$.This model is quite natural, as it extends both the Waring model $f = \sum \alpha_i \ell_i^d$ , and the sparsest shift model $f = \sum \alpha_i \ell^{e_i}$, but it is still not well known.In this work, we obtained structural results for the univariate variant of this model, which allow us to obtain lower bounds and reconstruction algorithms, that solve the following problem : given $f = \sum \alpha_i (x-a_i)^{e_i}$ as a list of its coefficient, find the values of the $\alpha_i$’s, $e_i$’s and $a_i$’s in the optimal decomposition of $f$.We also studied the multivariate case and obtained several reconstruction algorithms that work whenever the number of terms in the optimal expression is small in terms of the number of variable or the degree of the polynomial
39
Zhang, Weijian. "Evolving graphs and similarity-based graphs with applications." Thesis, University of Manchester, 2018. https://www.research.manchester.ac.uk/portal/en/theses/evolving-graphs-and-similaritybased-graphs-with-applications(66a23d3d-1ad0-454b-9ba0-175b566af95d).html.
Full textAbstract:
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.
40
Dénès, Maxime. "Étude formelle d'algorithmes efficaces en algèbre linéaire." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00945775.
Full textAbstract:
Les méthodes formelles ont atteint un degré de maturité conduisant à la conception de systèmes de preuves généralistes, permettant à la fois de vérifier la correction de systèmes logiciels complexes ou de formaliser des mathématiques avancées. Mais souvent, l'accent est mis davantage sur la facilité du raisonnement sur les programmes plutôt que sur leur exécution efficace. L'antagonisme entre ces deux aspects est particulièrement sensible pour les algorithmes de calcul formel, dont la correction repose habituellement sur des concepts mathématiques élaborés, mais dont l'efficacité pratique est une préoccupation importante. Cette thèse développe des approches à l'étude formelle et l'exécution efficace de programmes en théorie des types, et plus précisément dans l'assistant à la preuve \coq{}. Dans un premier temps, nous présentons un environnement d'exécution permettant de compiler en code natif de tels programmes tout en conservant la généralité et l'expressivité du formalisme. Puis, nous nous intéressons aux représentations de données et plus particulièrement au lien formellement vérifié et automatisé entre représentations adaptées aux preuves ou au calcul. Ensuite, nous mettons à profit ces techniques pour l'étude d'algorithmes en algèbre linéaire, comme le produit matriciel de Strassen, le procédé d'élimination de Gauss ou la mise en forme canonique de matrices, dont notamment la forme de Smith pour les matrices sur un anneau euclidien. Enfin, nous ouvrons le champ des applications à la formalisation et au calcul certifié des groupes d'homologie de complexes simpliciaux issus d'images numériques.
41
Sidhom, Lilia. "Sur les différentiateurs en temps réel : algorithmes et applications." Phd thesis, INSA de Lyon, 2011. http://tel.archives-ouvertes.fr/tel-00701576.
Full textAbstract:
La qualité de la dérivation numérique en ligne d'un signal bruité joue un rôle primordial dans diverses applications touchant différents domaines (1D et 2D). Dans le travail présenté, nous nous sommes intéressés aux dérivateurs type "signal". Nos travaux s'inscrivent dans ce contexte et abordent des aspects théoriques et applicatifs. Du point de vue théorique, une étude de deux familles de dérivateurs a été effectuée. En premier lieu, nous avons étudié les dérivateurs de nature algébrique [travaux du projet INRIA-Non-A] et en deuxième lieu les différentiateurs modes glissants d'ordre supérieur [travaux de Levant]. Cette étude nous a permis de décrire les points forts et les points faibles de chacune de ces approches. Suite à cette étude, une nouvelle version des dérivateurs modes glissants a été proposée. Du point de vue applicatif, une première application dans le domaine 1D est présentée et qui consiste à utiliser le dérivateur proposé pour l'identification paramétrique en ligne d'un robot SCARA à deux axes. La méthode d'identification est validée expérimentalement par comparaison des résultats obtenus avec ceux donnés par d'autres méthodes (méthode en ligne et hors ligne). La deuxième application touche au domaine 2D. Dans ce cas, nous proposons l'application du différentiateur pour la détection des contours dans une image. Pour la validation des résultats, différents essais sont réalisés pour différents types de bruits. Une étude comparative avec des méthodes classiques est effectuée. Pour pouvoir tester l'efficacité du différentiateur dans des boucles de commande nous nous sommes intéressés aux systèmes électrohydrauliques. Le système physique étudié est un servo-vérin électrohydraulique à hautes performances ayant différents modes de fonctionnement. Après une succession d'hypothèses effectuées sur le modèle de simulation, des modèles de commande sont fournis. La dernière partie de ces travaux est dédiée à la synthèse de stratégie de commande via la technique du Backstepping pour le positionnement de l'axe électrohydraulique afin de tester l'efficacité l'algorithme proposé dans des boucles de commande. Comme base de comparaison, la version classique des algorithmes modes glissants est aussi utilisée.
42
Rémy, Adrien. "Solving dense linear systems on accelerated multicore architectures." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112138/document.
Full textAbstract:
Dans cette thèse de doctorat, nous étudions des algorithmes et des implémentations pour accélérer la résolution de systèmes linéaires denses en utilisant des architectures composées de processeurs multicœurs et d'accélérateurs. Nous nous concentrons sur des méthodes basées sur la factorisation LU. Le développement de notre code s'est fait dans le contexte de la bibliothèque MAGMA. Tout d'abord nous étudions différents solveurs CPU/GPU hybrides basés sur la factorisation LU. Ceux-ci visent à réduire le surcoût de communication dû au pivotage. Le premier est basé sur une stratégie de pivotage dite "communication avoiding" (CALU) alors que le deuxième utilise un préconditionnement aléatoire du système original pour éviter de pivoter (RBT). Nous montrons que ces deux méthodes surpassent le solveur utilisant la factorisation LU avec pivotage partiel quand elles sont utilisées sur des architectures hybrides multicœurs/GPUs. Ensuite nous développons des solveurs utilisant des techniques de randomisation appliquées sur des architectures hybrides utilisant des GPU Nvidia ou des coprocesseurs Intel Xeon Phi. Avec cette méthode, nous pouvons éviter l'important surcoût du pivotage tout en restant stable numériquement dans la plupart des cas. L'architecture hautement parallèle de ces accélérateurs nous permet d'effectuer la randomisation de notre système linéaire à un coût de calcul très faible par rapport à la durée de la factorisation. Finalement, nous étudions l'impact d'accès mémoire non uniformes (NUMA) sur la résolution de systèmes linéaires denses en utilisant un algorithme de factorisation LU. En particulier, nous illustrons comment un placement approprié des processus légers et des données sur une architecture NUMA peut améliorer les performances pour la factorisation du panel et accélérer de manière conséquente la factorisation LU globale. Nous montrons comment ces placements peuvent améliorer les performances quand ils sont appliqués à des solveurs hybrides multicœurs/GPUIn this PhD thesis, we study algorithms and implementations to accelerate the solution of dense linear systems by using hybrid architectures with multicore processors and accelerators. We focus on methods based on the LU factorization and our code development takes place in the context of the MAGMA library. We study different hybrid CPU/GPU solvers based on the LU factorization which aim at reducing the communication overhead due to pivoting. The first one is based on a communication avoiding strategy of pivoting (CALU) while the second uses a random preconditioning of the original system to avoid pivoting (RBT). We show that both of these methods outperform the solver using LU factorization with partial pivoting when implemented on hybrid multicore/GPUs architectures. We also present new solvers based on randomization for hybrid architectures for Nvidia GPU or Intel Xeon Phi coprocessor. With this method, we can avoid the high cost of pivoting while remaining numerically stable in most cases. The highly parallel architecture of these accelerators allow us to perform the randomization of our linear system at a very low computational cost compared to the time of the factorization. Finally we investigate the impact of non-uniform memory accesses (NUMA) on the solution of dense general linear systems using an LU factorization algorithm. In particular we illustrate how an appropriate placement of the threads and data on a NUMA architecture can improve the performance of the panel factorization and consequently accelerate the global LU factorization. We show how these placements can improve the performance when applied to hybrid multicore/GPU solvers
43
Tisseur, Françoise. "Méthodes numériques pour le calcul d'éléments spectraux : étude de la précision, la stabilité et la parallélisation." Saint-Etienne, 1997. http://www.theses.fr/1997STET4006.
Full textAbstract:
Cette thèse est constituée de deux parties. La première traite de la méthode QR pour le calcul de valeurs propres de matrices quelconques, de tailles modérées. Les contributions originales à ce sujet sont a) une preuve rigoureuse de sa stabilité inverse, b) un nouveau critère d'arrêt justifié par une analyse mathématique. La seconde partie traite de la méthode de Yau et Lu pour le calcul de valeurs propres de matrices symétriques réelles de grandes tailles. Les contributions dans ce travail à ce sujet sont a) une compréhension mathématique accrue de la méthode, b) sa validation numérique, c) une proposition de parallélisation
44
Seiller, Thomas. "Logique dans le facteur hyperfini : Géométrie de l' interaction et complexité." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4064.
Full textAbstract:
Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisissant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions — qui semblent à première vue si différentes — sont des conséquences d'une même identité géométriqueThis work is a study of the geometry of interaction in the hyperfinite factor introduced by Jean-Yves Girard, and of its relations with ancient constructions. We start by showing how to obtain purely geometrical adjunctions as an identity between sets of cycles appearing between graphs. It is then possible, by chosing a function that measures those cycles, to obtain a numerical adjunction. We then show how to construct, on the basis of such a numerical adjunction, a geometry of interaction for multiplicative additive linear logic where proofs are interpreted as graphs. We also explain how to define from this construction a denotational semantics for MALL, and a notion of truth. We extend this setting in order to deal with exponential connectives and show a full soundness result for a variant of elementary linear logic (ELL). Since the constructions on graphs we define are parametrized by a function that measures cycles, we then focus our study to two particular cases. The first case turns out to be a combinatorial version of GoI5, and we thus obtain a geometrical caracterisation of its orthogonality which is based on Fuglede-Kadison determinant. The second particular case we study will giveus a refined version of older constructions of geometry of interaction, where orthogonality is based on nilpotency. This allows us to show how these two versions of GoI, which seem quite different, are related and understand that the respective adjunctions are both consequences of a unique geometrical property. In the last part, we study the notion of subjective truth
45
Sedoglavic, Alexandre. "Méthodes seminumériques en algèbre différentielle; applications à l'étude des propriétés structurelles de systèmes différentiels algébriques en automatique." Phd thesis, Ecole Polytechnique X, 2001. http://tel.archives-ouvertes.fr/tel-00401888.
Full textAbstract:
Les travaux présentés dans ce mémoire se basent sur les apports de l'algèbre différentielle et les méthodes du calcul symbolique pour résoudre des problèmes d'automatique non linéaire qui ne se prêtent pas à une résolution numérique directe.Le problème de l'observabilité algébrique locale consiste à décider si les variables d'état intervenant dans un modèle peuvent être déterminées en fonction des entrées et des sorties supposées parfaitement connues.
Nous présentons un algorithme probabiliste de complexité arithmétique polynomiale en la taille de l'entrée permettant de tester l'observabilité algébrique locale en déterminant les variables non observables. L'utilisation du calcul modulaire permet d'obtenir pour ce test une complexité binaire elle aussi polynomiale. Cette complexité dépend linéairement de la probabilité de succès qui peut être arbitrairement fixée. Une implantation de cet algorithme permet de traiter des problèmes inaccessibles jusqu'à présent.
À partir de ces méthodes mêlant calcul symbolique et calcul numérique, nous proposons une généralisation de la notion de platitude différentielle à certains modèles non linéaires décrits par des équations aux dérivées partielles. Un système différentiel ordinaire est différentiellement plat si ses solutions peuvent être localement paramétrées bijectivement par des fonctions arbitraires.
Pour étudier certains systèmes d'équations aux dérivées partielles non linéaires, on se ramène à un système d'équations différentielles ordinaires par discrétisation ; notre approche consiste à chercher des discrétisations plates telles que les paramétrages associés convergent lorsque le pas de discrétisation tend vers zéro. Cette méthode est illustrée par l'étude du problème de planification de trajectoire réalisée pour trois modèles non linéaires de dimension infinie : l'équation de la chaleur semilinéaire, l'équation de Burger avec diffusion et un modèle non linéaire de tige flexible.
46
Bientinesi, Paolo. "Mechanical derivation and systematic analysis of correct linear algebra algorithms." Thesis, 2006. http://hdl.handle.net/2152/2679.
Full text
47
Tropp, Joel Aaron. "Topics in sparse approximation." Thesis, 2004. http://hdl.handle.net/2152/1272.
Full text
48
Tropp, Joel Aaron Dhillon Inderjit S. Gilbert Anna C. "Topics in sparse approximation." 2004. http://wwwlib.umi.com/cr/utexas/fullcit?p3143480.
Full text
49
Gunnels, Joseph Andrew. "A systematic approach to the design and analysis of linear algebra algorithms." 2001. http://hdl.handle.net/2152/10503.
Full text
50
Yamamoto, Yusaku. "High performance algorithms for numerical linear algebra." Thesis, 2003. http://hdl.handle.net/2237/6641.
Full text