Item – Theses Canada

​
OCLC number
1032913708
Link(s) to full text
LAC copy
LAC copy
Author
Li, Chao,1983-
Title
Lattice Compression of Polynomial Matrices.
Degree
Master of Mathematics -- University of Waterloo, 2007
Publisher
Waterloo : University of Waterloo, 2007.
Description
1 online resource
Notes
Includes bibliographical references.
Abstract
This thesis investigates lattice compression of polynomial matrices over finite fields. For an m x n matrix, the goal of lattice compression is to find an m x (m+k) matrix, for some relatively small k, such that the lattice span of two matrices are equivalent. For any m x n polynomial matrix with degree bound d, it can be compressed by multiplying by a random n x (m+k) matrix B with degree bound s. In this thesis, we prove that there is a positive probability that L(A)=L(AB) with k(s+1)=\Theta(\log(md)). This is shown to hold even when s=0 (i.e., where B is a matrix of constants). We also design a competitive probabilistic lattice compression algorithm of the Las Vegas type that has a positive probability of success on any input and requires O~(nm^{\theta-1}B(d)) field operations.
Other link(s)
hdl.handle.net
uwspace.uwaterloo.ca
uwspace.uwaterloo.ca
Subject
Polynomial matrices.
Lattice compression.
Randomize.
Computer Science.