<?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-22T10:32:14Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/7326" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/7326</identifier><datestamp>2017-03-21T14:51:17Z</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="author" authority="450b9cab-1f29-455f-9745-59f6a1d1e930" confidence="600">Zhou, Wei</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2013-01-28T16:03:52Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2013-01-28T16:03:52Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2013-01-28T16:03:52Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012-11-28</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/7326</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this thesis, we present efficient deterministic algorithms&#xd;
for polynomial matrix computation problems, including the computation&#xd;
of order basis, minimal kernel basis, matrix inverse, column basis,&#xd;
unimodular completion, determinant, Hermite normal form, rank and&#xd;
rank profile for matrices of univariate polynomials over a field.&#xd;
The algorithm for kernel basis computation also immediately provides&#xd;
an efficient deterministic algorithm for solving linear systems. The&#xd;
algorithm for column basis also gives efficient deterministic algorithms&#xd;
for computing matrix GCDs, column reduced forms, and Popov normal&#xd;
forms for matrices of any dimension and any rank. &#xd;
&#xd;
&#xd;
We reduce all these problems to polynomial matrix multiplications.&#xd;
The computational costs of our algorithms are then similar to the&#xd;
costs of multiplying matrices, whose dimensions match the input matrix&#xd;
dimensions in the original problems, and whose degrees equal the average&#xd;
column degrees of the original input matrices in most cases. The use&#xd;
of the average column degrees instead of the commonly used matrix&#xd;
degrees, or equivalently the maximum column degrees, makes our computational&#xd;
costs more precise and tighter. In addition, the shifted minimal bases&#xd;
computed by our algorithms are more general than the standard minimal&#xd;
bases.</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">polynomial matrix computation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">computer algebra</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">order basis</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">kernel basis</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">linear system solving</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">matrix inverse</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">determinant</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">unimodular completion</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Popov form</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Hermite form</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">column reduced form</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">GCD</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">matrix GCD</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">rank</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">rank profile</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">column basis</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Fast Order Basis and Kernel Basis Computation and Related Problems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</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>