Item – Theses Canada

​
OCLC number
608932975
Link(s) to full text
LAC copy
LAC copy
Author
Li, Chao,1983-
Title
Lattice compression of polynomial matrices.
Degree
M. Math. -- University of Waterloo, 2007
Publisher
Ottawa : Library and Archives Canada = Bibliothèque et Archives Canada, [2008]
Description
1 microfiche
Notes
Includes bibliographical references.
Abstract
This thesis investigates lattice compression of polynomial matrices over finite fields. For an 'm' * 'n' matrix, the goal of lattice compression is to find an 'm' * (' m'+'k') matrix, for some relatively small ' k', such that the lattice span of two matrices are equivalent. For any 'm' * 'n' polynomial matrix with degree bound 'd', it can be compressed by multiplying by a random ' n' * ('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]-1B('d')) field operations.
ISBN
9780494343425
0494343427