<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T16:53:32Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/17514" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/17514</identifier><datestamp>2025-03-26T23:35:09Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Labahn, George</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Storjohann, Arne</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="47e91005-9135-4a37-81a2-3d2b9c766f35" confidence="600">Birmpilis, Stavros</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2021-09-24T15:06:59Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2021-09-24T15:06:59Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2021-09-24</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2021-09-20</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/17514</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The focus of this thesis is on fundamental computational problems in exact integer linear algebra. Specifically, for a nonsingular integer input matrix A of dimension n, we consider problems such as linear system solving and computing integer matrix normal forms.&#xd;
Our goal is to design algorithms that have complexity about the same as the cost of multiplying together two integer matrices of the same dimension and size of entries as the input matrix A. If 2 ≤ ω ≤ 3 is a valid exponent for matrix multiplication, that is, if two n × n matrices can be multiplied in O(n^ω) basic operations from the domain of entries, then our target complexity is O(n^ω log ||A||) bit operations, up to some missing log n and loglog ||A|| factors. Here ||A|| denotes the largest entry in A in absolute value.&#xd;
The first contribution is solving the problem of computing the Smith normal form S of a nonsingular matrix A along with computing unimodular matrices U, V such that AV = US within our target cost. The algorithm we give is a Las Vegas probabilistic algorithm which means that we are able to verify the correctness of its output.&#xd;
The second contribution of the thesis is with respect to linear system solving. We present a deterministic reduction to matrix multiplication for the problem of linear system solving: given as input a nonsingular A and a vector b, solve the system Ax = b. The system solution x is computed within our target complexity.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Smith normal form</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Integer matrices</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Linear system solving</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Exact linear algebra</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Fast algorithms for computing with integer matrices: normal forms and applications</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Labahn, George</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Storjohann, Arne</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>