The asymptotically fastest algorithms for many linear algebra problems on integer matrices, including solving a system of linear equations and computing the determinant, use high-order lifting. For a square nonsingular integer matrix A, high-order lifting computes B congruent to A^{-1} mod X^k and matrix R with AB = I + RX^k for non-negative integers X and k. Here, we present a deterministic method -- "double-plus-one" lifting -- to compute the high-order residue R as well as a succinct representation of B. As an application, we give a fully deterministic algorithm to certify the unimodularity of A. The cost of the algorithm is O((log n) n^{omega} M(log n + log ||A||)) bit operations, where ||A|| denotes the largest entry in absolute value, M(t) the cost of multiplying two integers bounded in bit length by t, and omega the exponent of matrix multiplication. Unimodularity certification is then applied to give a heuristic, but certified, algorithm for computing the determinant and Hermite normal form of a square, nonsingular integer matrix. Though most effective on random matrices, a highly optimized implementation of the latter algorithm demonstrates the techniques' effectiveness across a variety of inputs: empirical running times grow as O(n^3log n). A comparison against the fastest known Hermite normal algorithms -- those available in Sage and Magma -- show our implementation is, in all cases, highly competitive, and often surpasses existing, state-of-the-art implementations.

Thesis (M.A.)--Boston University / This paper, utilizing the properties of Vector spaces, describes an approach to polynomial approximations of functions defined analytically or by a set of observations over some interval. If the function and its approximation are both considered tobe elements of a linear normed vector space, a weighted sum or integral of the square of the discrepancy between the function and its approximation is to be a minimum. When this condition is satisfied, and depending upon the interval of interest, the polynomial approximation to the function becomes either the Legendre, Chebyshev, Laguerre, or hermite approximation formulas. An investigation into the properties and applications of these formulas is included, and it is shown that these formulas give the best polynomial approximations to certain functions in the sense of least squares.

The asymptotically fastest algorithms for many linear algebra problems on integer matrices, including solving a system of linear equations and computing the determinant, use high-order lifting. For a square nonsingular integer matrix A, high-order lifting computes B congruent to A^{-1} mod X^k and matrix R with AB = I + RX^k for non-negative integers X and k. Here, we present a deterministic method -- "double-plus-one" lifting -- to compute the high-order residue R as well as a succinct representation of B. As an application, we give a fully deterministic algorithm to certify the unimodularity of A. The cost of the algorithm is O((log n) n^{omega} M(log n + log ||A||)) bit operations, where ||A|| denotes the largest entry in absolute value, M(t) the cost of multiplying two integers bounded in bit length by t, and omega the exponent of matrix multiplication. Unimodularity certification is then applied to give a heuristic, but certified, algorithm for computing the determinant and Hermite normal form of a square, nonsingular integer matrix. Though most effective on random matrices, a highly optimized implementation of the latter algorithm demonstrates the techniques' effectiveness across a variety of inputs: empirical running times grow as O(n^3log n). A comparison against the fastest known Hermite normal algorithms -- those available in Sage and Magma -- show our implementation is, in all cases, highly competitive, and often surpasses existing, state-of-the-art implementations.

<p>This thesis deals with the design and implementation of some novel numerical methods for non-linear singular pertubations problems (NSPPs). It provide a survey of asymptotic and numerical methods for some NSPPs in the past decade. By considering two test problems, rigorous asymptotic analysis is carried out. Based on this analysis, suitable numerical methods are designed, analyzed and implemented in order to have some relevant results of physical importance. Since the asymptotic analysis provides only qualitative information, the focus is more on the numerical analysis of the problem which provides the quantitative information.</p>

<p>This thesis deals with the design and implementation of some novel numerical methods for non-linear singular pertubations problems (NSPPs). It provide a survey of asymptotic and numerical methods for some NSPPs in the past decade. By considering two test problems, rigorous asymptotic analysis is carried out. Based on this analysis, suitable numerical methods are designed, analyzed and implemented in order to have some relevant results of physical importance. Since the asymptotic analysis provides only qualitative information, the focus is more on the numerical analysis of the problem which provides the quantitative information.</p>

Thesis (M. Sc.)--University of the Western Cape, 2007. / Includes bibliographical references (leaves 61-77).

This thesis demonstrates an efficient parallel method of solving the generalized eigenvalue problem, KΦ = M ΦΛ, where K is symmetric and M is symmetric positive-definite, by first converting it to a standard eigenvalue problem, solving the standard eigenvalue problem, and back-transforming the results. An abstraction for parallel dense linear algebra is introduced along with a new algorithm for forming A := U⁻ᵀ K U⁻¹ , where U is the Cholesky factor of M , that is up to twice as fast as the ScaLAPACK implementation. Additionally, large improvements over the PBLAS implementations of general matrix-matrix multiplication and triangular solves with many right-hand sides are shown. Significant performance gains are also demonstrated for Cholesky factorizations, and a case is made for using 2D-cyclic distributions with a distribution blocksize of one. / text

Families of linear functionals on a vector space that are mapped to each other by a group of symmetries of the space have a significant amount of structure. This results in computational redundancies which can be used to make computing the entire family of functionals at once more efficient than applying each in turn. This thesis explores asymptotic complexity results for a few such families: contingency tables and unranked choice data. These are used to explore the framework of Radon transform diagrams, which promise to allow general theorems about linear summary statistics to be stated and proved.

This paper deals with the design of multi-axis force (also known as force/torque) sensors, as considered within the framework of optimal design theory. The principal goal of this paper is to identify a mathematical objective function, whose minimization corresponds to the optimization of sensor accuracy. The methodology employed is derived from linear algebra and analysis of numerical stability. The problem of optimizing the number of basic transducers employed in a multi-component sensor is also addressed. Finally, applications of the proposed method to the design of a simple sensor as well as to the optimization of a novel, 6-axis miniaturized sensor are discussed.

This thesis is devoted to investigation of some properties of the permanent function over the set Omega_n of n-by-n doubly stochastic matrices. It contains some basic properties as well as some partial progress on Foregger's conjecture. CONJECTURE[Foregger] For every n\in N, there exists k=k(n)>1 such that, for every matrix A\in Omega_n, per(A^k)<=per(A). In this thesis the author proves the following result. THEOREM For every c>0, n\in N, for all sufficiently large k=k(n,c), for all A\in\Omega_n which minimum nonzero entry exceeds c, per(A^k)<=per(A). This theorem implies that for every A\in\Omega_n, there exists k=k(n,A)>1 such that per(A^k)<=per(A).