published_or_final_version / Chemistry / Doctoral / Doctor of Philosophy

published_or_final_version / Chemistry / Doctoral / Doctor of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

No description available.

Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.

The basis handling procedures of the simplex method are formulated in terms of a "double basis". That is, the basis is factored as (DIAGRAM OMITTED...PLEASE SEE DAI) where ‘B, the pseudobasis matrix, is the basis matrix at the last refactorization. P and Q are permutation matrices. Forward and backward transformations and update are presented for each of two implementations of the double-basis method. The first implementation utilizes an explicit G⁻¹ matrix. The second uses a sparse LU factorization of G. Both are based on Marsten's modularized XMP package, in which standard simplex method routines are replaced by corresponding double-basis method routines. XMP and the LU double-basis method implementation employ Reid's LA05 routines for handling sparse linear programming bases. All calculations are done without reference to the H matrix. Therefore, the update is restricted to G, which has dimension limited by the refactorization frequency, and P and Q, which are held as lists. This can lead to a saving in storage space and updating time. The cost is that time for transformations will be about double. Computational comparisons of storage and speed performance are made with the standard simplex method on problems of up to 1480 constraints. It is found that, generally, the double-basis method performs best on larger, denser problems. Density seems to be the more important factor, and the problems with large nonzero growth between refactorizations are the better ones for the double-basis method. Storage saving in the basis inverse representation versus the standard method is as high as 36%, whereas the double-basis run times are 1.2 or more times as great.

We generalise the study of cyclotomic matrices - those with all eigenvalues in the interval [-2; 2] - from symmetric rational integer matrices to Hermitian matrices with entries from rings of integers of imaginary quadratic fields. As in the rational integer case, a corresponding graph-like structure is defined. We introduce the notion of `4-cyclotomic' matrices and graphs, prove that they are necessarily maximal cyclotomic, and classify all such objects up to equivalence. Six rings OQ( p d) for d = -1;-2;-3;-7;-11;-15 give rise to examples not found in the rational-integer case; in four (d = -1;-2;-3;-7) we recover infinite families as well as sporadic cases. For d = -15;-11;-7;-2, we demonstrate that a maximal cyclotomic graph is necessarily 4- cyclotomic and thus the presented classification determines all cyclotomic matrices/graphs for those fields. For the same values of d we then identify the minimal noncyclotomic graphs and determine their Mahler measures; no such graph has Mahler measure less than 1.35 unless it admits a rational-integer representative.

A dissertation submitted to the faculty of science, University of the Witwatersrand, Johannesburg, in fulfillment of the requirements for the degree of Master of Science. July 6, 2017. / We study the collective field theory of a free multi-matrix model in the radial sector, which has an emergent 1/r2 term, and take the large N limit. We show that it is possible to generate 2−d metrics with generic dependence on the collective field Lagrange multiplier (μ) and potential and which are distinguished by the choice of the potential. The Lagrange multiplier is shown to depend on an induced scale parameter after an I.R. regularization and breaks scale invariance. The collective field sl(2, R) algebras of the free Hamiltonian and a related alternative compact operator only close in the absence of μ. We point out that the broken conformal symmetry is contained in the associated metrics which suggests that they are related to a Near-AdS2 geometry. We also comment on the resemblance of these metrics to black hole solutions. / MT2018

A research report submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in partial fulfilment of the requirements for the degree of Master of Science. / This research report serves as an introduction to the concept of Operator Spaces which has gained considerable momentum in its acknowledgement and research interest in the last few decades. It will highlight a very important breakthrough on the characterization of Operator spaces which occurred in the !ast few years brought about by Z.J. Ruan. It investigates the relationship of this space in relation to Banach space theory by looking at an extension theorem for linear functionals, / Andrew Chakane 2018

Kirchhoff's laws are well-studied for electrical networks with voltage and current sources, and edges marked by resistors. Kirchhoff's voltage law states that the sum of voltages around any circuit of the network graph is zero, while Kirchhoff's current law states that the sum of the currents along any cutset of the network graph is zero. Given a network, these requirements may be encoded by the circuit matrix and cutset matrix of the network graph. The columns of these matrices are indexed by the edges of the network graph, and their row spaces are orthogonal complements. For (chemical or electrochemical) reaction networks, one must naturally study the opposite problem, beginning with the stoichiometric matrix rather than the network graph. This leads to the following question: given such a matrix, what is a suitable graphic rendering of a network that properly visualizes the underlying chemical reactions? Although we can not expect uniqueness, the goal is to prove existence of such a graph for any matrix. Specifically, we study Kirchhoff graphs, originally introduced by Fehribach. Mathematically, Kirchhoff graphs represent the orthocomplementarity of the row space and null space of integer-valued matrices. After introducing the definition of Kirchhoff graphs, we will survey Kirchhoff graphs in the context of several diverse branches of mathematics. Beginning with combinatorial group theory, we consider Cayley graphs of the additive group of vector spaces, and resolve the existence problem for matrices over finite fields. Moving to linear algebra, we draw a number of conclusions based on a purely matrix-theoretic definition of Kirchhoff graphs, specifically regarding the number of vector edges. Next we observe a geometric approach, reviewing James Clerk Maxwell's theory of reciprocal figures, and presenting a number of results on Kirchhoff duality. We then turn to algebraic combinatorics, where we study equitable partitions, quotients, and graph automorphisms. In addition to classifying the matrices that are the quotient of an equitable partition, we demonstrate that many Kirchhoff graphs arise from equitable edge-partitions of directed graphs. Finally we study matroids, where we review Tutte's algorithm for determining when a binary matroid is graphic, and extend this method to show that every binary matroid is Kirchhoff. The underlying theme throughout each of these investigations is determining new ways to both recognize and construct Kirchhoff graphs.