A number of recent developments has increased the desirability of using exclusive OR (XOR) gates in the synthesis of switching functions. This has, in turn, led naturally to an increased interest in algorithms for the minimization of Exclusive-Or Sum of Products (ESOP) forms. Although this is an active area of research, it is not nearly as developed as the traditional Sum of Products forms. Computer programs to find minimum ESOPs are not readily available and those that do exist are impractical to use as investigative tools because they are too slow and/or require too much memory. A practical tool would be easy enough to use (faster/smaller) so that it could be run many times to explore the solution space of the minimization problem as well as to provide a baseline of comparison. This thesis develops and investigates such a tool.

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than the minimal form of KRM expansion. • It is a sub-class of the Generalized Reed-Muller Expansion, thus has better testibility than other AND/EXOR circuits. Those design methods of easily testable GRM circuit networks[ 6] [35] can also be used for this new circuit form. • The exact solution to the minimization of this new expansion provides a upperbound for the minimization of ORM expansion. In this thesis, we prove that to calculate a PMPRM expansion from one of its adjacent polarity expansion , only one EXOR operation is needed. By calculating the adjacent polarity expansions one-by-one and searching all the PMPRM forms the minimum one can be found. A speedup approach allows us to find the exact minimum PMPRM without calculating all forms. The algorithm is explained by minimizing the 3-variable functions and is demonstrated by flow graphs. With the introduction of termwise complementary expansion diagram, a computerized algorithm for the calculation of any ORM expansion is presented. The exact minimum ORM form can be obtained by an exhaustive search through all ORM forms. A heuristic minimization algorithm, which is designed to decrease the time complexity of the exact one, is also presented in this thesis. Instead of depending on the number of input variables, the computation time of this quasi-minimum algorithm depends mainly on the complexity of the input functions, thus can solve much larger problems. The exact minimization algorithm for PMPRM and the quasi-minimum ORM minimization algorithm have been implemented in C programs and a set of benchmark functions has been tested. The results are compared to those from [16], [36], and Espresso's. In most cases our program gives the same or better solutions.

Thesis advisor: Cowles, Mary K. Includes bibliographic references (p. 167-172).

Numerical techniques for linear systems arising from discretization of partial differential equations are nowadays essential for understanding the physical world. Among these techniques, iterative methods and the accompanying preconditioning techniques have become increasingly popular due to their great potential on large scale computation. In this work, we present preconditioning techniques for linear systems built with tensor product basis functions. Efficient algorithms are designed for various problems by exploiting the Kronecker product structure in the matrices, inherited from tensor product basis functions. Specifically, we design preconditioners for mass matrices to remove the complexity from the basis functions used in isogeometric analysis, obtaining numerical performance independent of mesh size, polynomial order and continuity order; we also present a compound iteration preconditioner for stiffness matrices in two dimensions, obtaining fast convergence speed; lastly, for the Helmholtz problem, we present a strategy to `hide' its indefiniteness from Krylov subspace methods by eliminating the part of initial error that corresponds to those negative generalized eigenvalues. For all three cases, the Kronecker product structure in the matrices is exploited to achieve high computational efficiency.

在這一篇論文中，我們討論 Ck/Cm/1 的等候系統。 我們利用矩陣多項式的奇異點及向量造 C_k/C_m/1 的機率分配的解空間。而矩陣多項式的非零奇異點和一個由抵達間隔時間與服務時間所形成的方程式有密切的關係。我們證明了在 E_k/E_m/1 的等候系統中，方程式的所有根都是相異的。但是當方程式有重根時，我們必須解一組相當複雜的方程式才能得到構成解空間的向量。此外，我們建立了一個描述飽和機率為 Kronecker products 線性組合的演算方法。 / In this thesis, we analyze the single server queueing system Ck/Cm/1. We construct a general solution space of the vector for stationary probability and describe the solution space in terms of singularities and vectors of the fundamental matrix polynomial Q(w). There is a relation between the singularities of Q(w) and the roots of the characteristic polynomial involving the Laplace transforms of the interarrival and service times distributions. In the Ek/Em/1 queueing system, it is proved that the roots of the characteristic polynomial are distinct if the arrival and service rates are real. When multiple roots occur, one needs to solve a set of equations of matrix polynomials. As a result, we establish a procedure for describing those vectors used in the expression of saturated probability as linear combination of Kronecker products.

This paper presents a detailed discussion of the Kronecker product of matrices. It begins with the definition and some basic properties of the Kronecker product. Statements will be proven that reveal information concerning the eigenvalues, singular values, rank, trace, and determinant of the Kronecker product of two matrices. The Kronecker product will then be employed to solve linear matrix equations. An investigation of the commutativity of the Kronecker product will be carried out using permutation matrices. The Jordan - Canonical form of a Kronecker product will be examined. Variations such as the Kronecker sum and generalized Kronecker product will be introduced. The paper concludes with an application of the Kronecker product to large least squares approximations.