I describe an exact method for computing roots of a system of multivariate polynomials with rational coefficients, called the rational univariate reduction. This method enables performance of exact algebraic computation of coordinates of the roots of polynomials. In computational geometry, curves, surfaces and points are described as polynomials and their intersections. Thus, exact computation of the roots of polynomials allows the development and implementation of robust geometric algorithms. I describe applications in robust geometric modeling. In particular, I show a new method, called numerical perturbation scheme, that can be used successfully to detect and handle degenerate configurations appearing in boundary evaluation problems. I develop a derandomized version of the algorithm for computing the rational univariate reduction for a square system of multivariate polynomials and a new algorithm for a non-square system. I show how to perform exact computation over algebraic points obtained by the rational univariate reduction. I give a formal description of numerical perturbation scheme and its implementation.

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 presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences.</p><p>Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an <em>O</em>(1.1730ⁿ) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in <em>O</em>(2^(1-<em>ε</em>⁾<em>n</em>) time, with 0 < <em>ε</em> < 1 for every fixed <em>i</em>; for <em>i</em>=2, 3 and 4 we have running times in <em>O</em>(1.4511ⁿ), <em>O</em>(1.6214ⁿ) and <em>O</em>(1.6848ⁿ) respectively.</p><p>For the counting problems we present an O(1.2190ⁿ) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SAT<em>w</em><em> </em>and #3SAT<em>w</em><em>,</em> two well studied Boolean problems. The algorithms have running times in O(1.2561ⁿ) and <em>O</em>(1.6737ⁿ) respectively.</p><p>Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SAT<em>w</em> without the addition of new variables and thus is solvable in time <em>O</em>(1.2561ⁿ). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348ⁿ) time.</p>

This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences. Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an O(1.1730n) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in O(2(1-ε) n) time, with 0 &lt; ε &lt; 1 for every fixed i; for i=2, 3 and 4 we have running times in O(1.4511n), O(1.6214n) and O(1.6848n) respectively. For the counting problems we present an O(1.2190n) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SATw and #3SATw, two well studied Boolean problems. The algorithms have running times in O(1.2561n) and O(1.6737n) respectively. Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SATw without the addition of new variables and thus is solvable in time O(1.2561n). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348n) time.

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.

In an attempt to generalize previous models of the bidirectional vortex mean flow, a new solution is presented that can cope with arbitrary injections and outlet conditions. In the process, the steady, inviscid and axisymmetric equations of motions are reduced to one partial differential equation for the stream function, known as the Bragg-Hawthorne equation, which is solved exactly. The solution is shown to be highly dependent on the imposed boundary conditions: the mean flow changes according to the manner by which the fluid is injected or extracted from the vortex chamber. From the stream function, the velocity is obtained along with the vorticity and pressure distributions which are carefully derived and analyzed. The results are then compared to several inviscid models found in the literature. After determining an exact inviscid solution to the problem, viscous effects at the core are added to overcome the known singularity that arises at the centerline. The governing equations are hence revisited while keeping the viscous diffusion term in the tangential momentum equation. The core region, where viscous effects lead to the onset of a forced vortex, is rescaled using appropriate transformations. An asymptotic approximation is then applied to linearize and solve the resulting ODE for the tangential vi velocity. The inner viscous solution is then matched to the outer inviscid result using Prandtl’s Matching Principle. Finally, the viscous correction is passed onto the vorticity and pressure formulations.

Spatial data occurs in several important and diverse applications in P2P systems, for example, P2P virtual cities, GIS, development planning, etc. For the problem of answering exact queries for spatial region data in the P2P environment, an R¡Vtree based structure probably is a good choice. However, since a peer system is dynamic, the global update characteristics of data insertion/deletion in an R¡Vtree can not work well in a P2P system. Moreover, the problem of overlaps in an R¡Vtree results in large number of the disk accesses (which will be considered as large number of messages in P2P systems). Therefore, a P2PR¡Vtree based indexing method for P2P systems has been proposed which has only local update to the proposed index structure when data insertion/deletion occurs. Although the P2PR¡Vtree can achieve the goal of the local update for data insertion/deletion, the overlapping phenomenon is still hard to solve. Recently, for region data access, an NA¡Vtree has been proposed which outperforms R¡Vtree¡Vlike data structures. Moreover, it does not have the problem of overlaps which may occur in an R¡Vtree. Basically, an NA¡Vtree does not split the spatial space, but it just classifies the spatial data objects by some rules. On the other hand, the Chord system is a well¡Vknown structured P2P system in which the data search is performed by a hash function, instead of flooding used in most of the unstructured P2P system. Since the Chord system is a hash approach, it is easy to deal with data insertion/deletion with only local update. However, the current Chord system can not work well with the region data, since it only works well with a single key value. Therefore, in this thesis, we propose to apply an NA-tree in the Chord system to encode spatial region data in the data key part used in the hash function to data search. That is, we still use one hash function of Chord to assign nodes to peers, and use another hash function to do data assignment by applying an NA¡Vtree to encode the spatial region data to data keys. First, we use three bits to present the first eight children in the NA¡Vtree. Next, we propose two methods to generate the key value of the remaining bits. For our first proposed method, it generates the remaining bits by adding 0¡¦s. This method is simple and applicable to the case that there are few objects in P2P systems. To avoid the case that a peer may own too many objects, the second method takes the central points of regions into consideration. This method is applicable to the case that there are too many objects in the P2P system. Finally, we concatenate the first three and the remaining bits to get the key values of objects. Thus, we combine the NA¡Vtree with the Chord system to solve the overlapping problem which the P2PR¡Vtree can not deal with. In our simulation study, we use six different data distributions to compare our method with the P2PR¡Vtree. From our simulation results, we show that the number of visited peers in our approach is less than that in the P2PR¡Vtree.

In this study we will consider the construction of approximate optimal design for one-dimensional regression by exchange algorithm. Sufficient conditions under which an optimal design must have the minimal support points are known in Theorem 2.3.2 of Fedorov (1972). However, there are only a few cases which the analytic optimal designs are known. The exchange procedure for computing optimal designs is easily adopted to most criteria. We describe implementations for constructing the well-known special cases D-, A-, and c-optimal designs with the minimum number of support points. Examples which illustrate how the algorithm can be used to obtain these optimal designs and the performance of the algorithm are discussed. The commonly used D-, A-, and c-optimal criteria will be employed to study the convergence properties of the exchange algorithm for regression model which the set of the product of regression functions forms a Chebyshev system.

In this thesis superconducting correlations on both a one-dimensional chain and a two-dimensional honeycomb lattice are analyzed using the t-J model Hamiltonian. Both systems use periodic boundary conditions and different electron fillings, and both are solved numerically using the Lanczos algorithm. In order to search for superconducting correlations in the ground state the pair-pair correlation and susceptibility functions are defined. In one dimension the correlation function, at lower electronic fillings, displayed appreciable, non-zero values for all pair-pair separations. In general, the one-dimensional results were consistent with the literature. However, the honeycomb results did not show such strong superconducting correlations, as the correlation function remained close to zero for most separation distances. / Thesis (Master, Physics, Engineering Physics and Astronomy) -- Queen's University, 2008-03-17 14:06:20.094

This thesis addresses the open questions of providing a cosmological model describing an accelerated expanding Universe without violating the energy conditions or a model that contributes to the physical interpretation of the dark energy. The former case is analyzed considering a closed model based on a regular lattice of black holes using the Einstein equation in vacuum. In the latter case I will connect the dark energy to the Shan-Chen equation of state. A comparison between these two proposals is then discussed. As a complementary topic I will discuss the motion of test particles in a general relativistic spacetime undergoing friction effects. This is modeled following the formalism of Poynting-Robertson whose link with the Stokes’ formula is presented. The cases of geodesic and non-geodesic motion are compared and contrasted for Schwarzschild, Tolman, Pant-Sah and Friedman metrics respectively.