Narrow Results

Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions d_n to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers d_n. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination problems are presented. Our approach actually solves the following more general problem: Given an arbitrary r× s integral matrix A and r-dimensional integral vectors b and c, let d_n(n=0,1,…) be the number of solutions in non-negative integers to the system Az=nb+c. Calculate the (rational) generating function ∑_{n≥ 0}d_ntⁿ and construct a formula for d_n.

We give a criterion for a monomial ideal in two variables to be complete (i.e. integrally closed) in terms of the exponents of the generators. This gives a positive answer to a question raised recently by P. Gimenez, A. Simis, W. Vasconcelos and R. Villarreal, On complete monomial ideals, J. Commut. Algebra, to appear, arXiv:1310.7793.

The first author defined a well-order in the set of links by embedding it into a canonical well-ordered set of (integral) lattice points. He also gave elementary transformations among lattice points to enumerate the prime links in terms of lattice points under this order. In this paper, we add some new elementary transformations and explain how to enumerate the prime links. We show a table of the first 443 prime links arising from the lattice points of lengths up to 10 under this order. Our argument enables us to find 7 omissions and 1 overlap in Conway's table of prime links of 10 crossings.

A well-order was introduced on the set of links by A. Kawauchi [3]. This well-order also naturally induces a well-order on the set of prime link exteriors and eventually induces a well-order on the set of closed connected orientable 3-manifolds. With respect to this order, we enumerated the prime links with lengths up to 10 and the prime link exteriors with lengths up to 9. Our present plan is to enumerate the 3–manifolds by using the enumeration of the prime link exteriors. In this paper, we show our latest result in this plan and as an application, give a new proof of the identification of Perko's pair.