Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"North Carolina State University" +contributor:("Erich Kaltofen, Committee Chair")`

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

North Carolina State University

1. Yuhasz, George Louis. Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences.

Degree: PhD, Mathematics, 2009, North Carolina State University

URL: http://www.lib.ncsu.edu/resolver/1840.16/3825

The Berlekamp/Massey algorithm computes the unique minimal generator of a
linearly generated scalar sequence. The matrix generalization of the Berlekamp/Massey
algorithm, the Matrix Berlekamp/Massey algorithm, computes a minimal matrix genera-
tor of a linearly generated matrix sequence. The Matrix Berlekamp/Massey algorithm has
applications in multivariable control theory and exact sparse linear algebra. The fraction
free version of the Matrix Berlekamp/Massey algorithm can be adapted into a linear solver
for block Hankel matrices. A thorough investigation of the Matrix Berlekamp/Massey algo-
rithm and the fraction free Matrix Berlekamp/Massey algorithm is presented. A description
of the algorithms and their invariants are given. The underlying linear algebra of the algo-
rithms is explored. The connection between the update procedures of the algorithms and
the nullspaces of the related matrix systems is detailed.
A full definition and description of linearly generated matrix sequences and their
various generators is given first as background. A new classification of all linearly generated
matrix sequences is proven to exist. A complete description of the Matrix Berlekamp/
Massey algorithm and its invariants is then given. We describe a new early termination
criterion for the algorithm and give a full proof of correctness for the algorithm. Our version
and proof of the algorithm removes all rank and dimension constraints present in previous
versions in the literature. Next a new variation of the Matrix Berlekamp/Massey algorithm
is described. The fraction free Matrix Berlekamp/Massey algorithm performs its operations
over integral domains. The divisions performed by the algorithm are exact. A full proof of
the algorithm and its exact division is given. Finally, we describe two implementations of the
Matrix Berlekamp/Massey algorithm, a Maple implementation and a C++ implementation,
and compare the two implementations. The C++ implementation is done in the generic
LinBox library for exact linear algebra and modeled after the Standard Template Library.
*Advisors/Committee Members: Dr. Agnes Szanto, Committee Member (advisor), Dr. Michael Singer, Committee Member (advisor), Dr. Ilse Ipsen, Committee Member (advisor), Dr. Erich Kaltofen, Committee Chair (advisor).*

Subjects/Keywords: exact linear algebra; linear recurrances; generic programming

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Yuhasz, G. L. (2009). Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences. (Doctoral Dissertation). North Carolina State University. Retrieved from http://www.lib.ncsu.edu/resolver/1840.16/3825

Chicago Manual of Style (16^{th} Edition):

Yuhasz, George Louis. “Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences.” 2009. Doctoral Dissertation, North Carolina State University. Accessed July 14, 2020. http://www.lib.ncsu.edu/resolver/1840.16/3825.

MLA Handbook (7^{th} Edition):

Yuhasz, George Louis. “Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences.” 2009. Web. 14 Jul 2020.

Vancouver:

Yuhasz GL. Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences. [Internet] [Doctoral dissertation]. North Carolina State University; 2009. [cited 2020 Jul 14]. Available from: http://www.lib.ncsu.edu/resolver/1840.16/3825.

Council of Science Editors:

Yuhasz GL. Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences. [Doctoral Dissertation]. North Carolina State University; 2009. Available from: http://www.lib.ncsu.edu/resolver/1840.16/3825

North Carolina State University

2. Turner, William J. Black Box Linear Algebra with the LinBox Library.

Degree: PhD, Computational Mathematics, 2002, North Carolina State University

URL: http://www.lib.ncsu.edu/resolver/1840.16/3025

Black box algorithms for exact linear algebra view a matrix as a linear operator on a vector space, gathering information about the matrix only though matrix-vector products and not by directly accessing the matrix elements. Wiedemann's approach to black box linear algebra uses the fact that the minimal polynomial of a matrix generates the Krylov sequences of the matrix and their projections. By preconditioning the matrix, this approach can be used to solve a linear system, find the determinant of the matrix, or to find the matrix's rank.
This dissertation discusses preconditioners based on Benes networks to localize the linear independence of a black box matrix and introduces a technique to use determinantal divisors to find preconditioners that ensure the cyclicity of nonzero eigenvalues. This technique, in turn, introduces a new determinant-preserving preconditioner for a dense integer matrix determinant algorithm based on the Wiedemann approach to black box linear algebra and relaxes a condition on the preconditioner for the Kaltofen-Saunders black box rank algorithm.
The dissertation also investigates the minimal generating matrix polynomial of Coppersmith's block Wiedemann algorithm, how to compute it using Beckermann and Labahn's Fast Power Hermite-Pade Solver, and a block algorithm for computing the rank of a black box matrix.
Finally, it discusses the design of the LinBox library for symbolic linear algebra.
*Advisors/Committee Members: Erich Kaltofen, Committee Chair (advisor), Carl D. Meyer, Committee Member (advisor), Ralph C. Smith, Committee Member (advisor), B. David Saunders, Committee Member (advisor), Hoon Hong, Committee Member (advisor).*

Subjects/Keywords: black box linear algebra; Wiedemann method; block Wiedemann method; linear algebra; randomized algorithm; LinBox library

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Turner, W. J. (2002). Black Box Linear Algebra with the LinBox Library. (Doctoral Dissertation). North Carolina State University. Retrieved from http://www.lib.ncsu.edu/resolver/1840.16/3025

Chicago Manual of Style (16^{th} Edition):

Turner, William J. “Black Box Linear Algebra with the LinBox Library.” 2002. Doctoral Dissertation, North Carolina State University. Accessed July 14, 2020. http://www.lib.ncsu.edu/resolver/1840.16/3025.

MLA Handbook (7^{th} Edition):

Turner, William J. “Black Box Linear Algebra with the LinBox Library.” 2002. Web. 14 Jul 2020.

Vancouver:

Turner WJ. Black Box Linear Algebra with the LinBox Library. [Internet] [Doctoral dissertation]. North Carolina State University; 2002. [cited 2020 Jul 14]. Available from: http://www.lib.ncsu.edu/resolver/1840.16/3025.

Council of Science Editors:

Turner WJ. Black Box Linear Algebra with the LinBox Library. [Doctoral Dissertation]. North Carolina State University; 2002. Available from: http://www.lib.ncsu.edu/resolver/1840.16/3025

North Carolina State University

3. May, John P. Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods.

Degree: PhD, Mathematics, 2005, North Carolina State University

URL: http://www.lib.ncsu.edu/resolver/1840.16/5379

Aspects of the approximate problem of finding the factors of a polynomial in many variables are considered. The idea is that an polynomial may be the result of a computation where a reducible polynomial was expected but due to introduction of floating point coefficients or measurement errors the polynomial is irreducible. Introduction of such errors will nearly always cause polynomials to become irreducible. Thus, it is important to be able to decide whether the computed polynomial is near to a polynomial that factors (and hence should be treated as reducible). If this is the case, one would like to be able to find a closest polynomial that does indeed factor.
Though this problem is computable there is no known polynomial time algorithm to find the nearest polynomial that factors. However, there are a number of methods that can be used to find a nearby polynomial that factors if the original polynomial was very close to being factorizable.
This dissertation gives a method to find a lower bound on the distance to the nearest polynomial that factors. If this lower bound is quite large, one can conclude that the polynomial does not have approximate factors. As part of finding this bound, a linear condition for irreducibility of polynomials from bivariate polynomials is generalized to polynomials with many variables, and a general theory of low rank approximation to extend bounds results to many different polynomial norms is given.
The singular value decomposition methods used to find the above lower bound can be used to create another method to find a nearby polynomial that factors. This method is studied, and is shown to be practical. Similar methods are also shown to work for approximate division and approximate greatest common divisor computation.
The results on bounding the distance to the nearest polynomial that factors can be applied to functional decomposition of univariate polynomials. Results on functional decomposition from the 1970's together with approximate factorization results allow for a method to compute a lower bound on the distance to the nearest polynomial that has a non-trivial functional decomposition and a new algorithm to compute approximate decompositions.
*Advisors/Committee Members: Erich Kaltofen, Committee Chair (advisor), Hoon Hong, Committee Member (advisor), Agnes Szanto, Committee Member (advisor), Pierre Gramaud, Committee Member (advisor), Mark Giesbrecht, Committee Member (advisor).*

Subjects/Keywords: numerical algebra; computer algebra; polynomial factorization; symbolic-numerics

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

May, J. P. (2005). Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods. (Doctoral Dissertation). North Carolina State University. Retrieved from http://www.lib.ncsu.edu/resolver/1840.16/5379

Chicago Manual of Style (16^{th} Edition):

May, John P. “Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods.” 2005. Doctoral Dissertation, North Carolina State University. Accessed July 14, 2020. http://www.lib.ncsu.edu/resolver/1840.16/5379.

MLA Handbook (7^{th} Edition):

May, John P. “Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods.” 2005. Web. 14 Jul 2020.

Vancouver:

May JP. Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods. [Internet] [Doctoral dissertation]. North Carolina State University; 2005. [cited 2020 Jul 14]. Available from: http://www.lib.ncsu.edu/resolver/1840.16/5379.

Council of Science Editors:

May JP. Approximate Factorization of Polynomials in Many Variables and Other Problems in Approximate Algebra via Singular Value Decomposition Methods. [Doctoral Dissertation]. North Carolina State University; 2005. Available from: http://www.lib.ncsu.edu/resolver/1840.16/5379