Sub-pixel distance maps and weighted distance transforms

A new framework for computing the Euclidean distance and weighted distance from the boundary of a given digitized shape is presented. The distance is calculated with sub-pixel accuracy. The algorithm is based on a equal distance contour evolution process. The moving contour is embedded as a level set in a time varying function of higher dimension. This representation of the evolving contour makes possible the use of an accurate and stable numerical scheme, due to Osher and Sethian [22]. The relation between the classical shape from shading problem and the weighted distance transform is presented, as well as an algorithm that calculates the geodesic distance transform on surfaces.     

Constructing Irreducible Representations of Finitely Presented Algebras

We describe an algorithmic test, using the “standard polynomial identity" (and elementary computational commutative algebra), for determining whether or not a finitely presented associative algebra has an irreducible n -dimensional representation. When n -dimensional irreducible representations do exist, our proposed procedure can (in principle) produce explicit constructions.     

Irreducible constituents of monomial representations

We describe an algorithm for obtaining the central primitive idempotents of the algebra associated with a monomial representation. As a consequence, we obtain its irreducible constituents. This is implemented in Magma, using an algorithm based on Dixon’s modular approach. In the case of permutation representations, we get a simplified version of the algorithms of Michler and Weller.     

Testing the irreducibility of nonsquare Perron–Frobenius systems

The Perron–Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.     

Accurate Solution of a System of Coupled Singularly Perturbed Reaction-diffusion Equations

We study a system of coupled reaction-diffusion equations. The equations have diffusion parameters of different magnitudes associated with them. Near each boundary, their solution exhibit two overlapping layers. A central difference scheme on layer-adapted piecewise uniform meshes is used to solve the system numerically. We show that the scheme is almost second-order convergent, uniformly in both perturbation parameters, thus improving previous results [5]. We present the results of numerical experiments to confirm our theoretical results.AMS Subject Classifications: 65L10, 65L11.     

AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures

This paper gives anO(n ²) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n ²) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.     

Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint

Conclusion  We have described an associative algorithm to find the smallest spanning tree of a graph with a degree constraint on one of the nodes. The associative algorithm is based on Gabow's algorithm. It is described as a STAR procedure that runs in timeO(@#@ nlogn). This is also the time it takes to construct a minimum spanning tree of a graph on an associative parallel processor [4]. The associative algorithm relies on a number of new constructions that are also useful for other problems. Note that, unlike [13], we use a very simple and natural data representation on an associative parallel processor in the form of two-dimensional binary-coded tables. Translated from Kibernetika i Sistemnyi Analiz, No. 1., pp. 94–103, January–February, 1998.     

A geometric approach for shared secrets, a refinement

A refinement to the (k,n) threshold scheme proposed by Wu and He [1] is presented. It has been found that usable primes p need not be confined to the form p ≡ ±3 (mod 8) as suggested originally. Our constructive proof also lead to a different algorithm for implementation. This implementation dispenses with the directory file suggested in [1] which can be prohibitively large when the scheme is implemented with large p using the original proposal.     

A binary operation on trees and an initial algebra characterization for finite tree types

Summary A binary operation on the class of trees is defined that generates a set B of finite trees form a trivial tree (one node) and B contains for every finite tree G exactly one element isomorphic to G. The binary operation defines an algebraic structure on B, and as a consequence the finite tree types are characterized as an initial algebra in the same way as the natural numbers are characterized as an initial algebra by the Peano-Lawvere axiom [2]. Simple and primitive recursion are defined and some applications of the initial algebra characterization are given.     

Decomposing Monomial Representations of Solvable Groups

We present an efficient algorithm that decomposes a monomial representation of a solvable groupG into its irreducible components. In contradistinction to other approaches, we also compute the decomposition matrixA in the form of a product of highly structured, sparse matrices. This factorization provides a fast algorithm for the multiplication with A. In the special case of a regular representation, we hence obtain a fast Fourier transform forG . Our algorithm is based on a constructive representation theory that we develop. The term “constructive" signifies that concrete matrix representations are considered and manipulated, rather than equivalence classes of representations as it is done in approaches that are based on characters. Thus, we present well-known theorems in a constructively refined form and derive new results on decomposition matrices of representations. Our decomposition algorithm has been implemented in the GAP share package AREP. One application of the algorithm is the automatic generation of fast algorithms for discrete linear signal transforms.     

On the equivalence and range of applicability of graph-based representations of logic programs

Logic programs under Answer Sets semantics can be studied, and actual computation can be carried out, by means of representing them by directed graphs. Several reductions of logic programs to directed graphs are now available. We compare our proposed representation, called Extended Dependency Graph, to the Block Graph representation recently defined by Linke [Proc. IJCAI-2001, 2001, pp. 641-648]. On the relevant fragment of well-founded irreducible programs, extended dependency and block graph turns out to be isomorphic. So, we argue that graph representation of general logic programs should be abandoned in favor of graph representation of well-founded irreducible programs, which are more concise, more uniform in structure while being equally expressive.     

Seat Reservation Allowing Seat Changes

We consider a new variant of the Seat Reservation Problem [4]in which seat changes are allowed. We analyze the problem using the competitive ratio and the competitive ratio on accommodating sequences [4]. A very promising algorithm defined in this paper is Min-Change, which will ask passengers to change seat, only if they would otherwise have been rejected. Min-Change belongs to a large class of conservative algorithms, for which we prove very high performance guarantees. For instance when assuming that all of the passengers could have been seated by an optimal off-line algorithm, at least of the passengers can be seated on-line with only one seat change and at least will be seated if two seat changes are allowed. This should be compared to the performance guarantee of for the best deterministic on-line algorithm when no seat changes are allowed [2].     

Renormalization Automated by Hopf Algebra

It was recently shown that the renormalization of quantum field theory is organized by the Hopf algebra of decorated rooted trees, whose coproduct identifies the divergences requiring subtraction and whose antipode achieves this. We automate this process in a few lines of recursive symbolic code, which deliver a finite renormalized expression for any Feynman diagram. We thus verify a representation of the operator product expansion, which generalizes Chen’s Lemma for iterated integrals. The subset of diagrams whose forest structure entails a unique primitive subdivergence provides a representation of the Hopf algebra H_Rof undecorated rooted trees. Our undecorated Hopf algebra program is designed to process the 24 213 878 BPHZ contributions to the renormalization of 7813 diagrams, with up to 12 loops. We consider 10 models, each in nine renormalization schemes. The two simplest models reveal a notable feature of the subalgebra of Connes and Moscovici, corresponding to the commutative part of the Hopf algebra H_Tof the diffeomorphism group: it assigns to Feynman diagrams those weights which remove zeta values from the counterterms of the minimal subtraction scheme. We devise a fast algorithm for these weights, whose squares are summed with a permutation factor, to give rational counterterms.     

Approximation of Geometric Dispersion Problems

We consider problems of distributing a number of points within a polygonal region P , such that the points are ``far away' from each other. Problems of this type have been considered before for the case where the possible locations form a discrete set. Dispersion problems are closely related to packing problems. While Hochbaum and Maass [20] have given a polynomial-time approximation scheme for packing, we show that geometric dispersion problems cannot be approximated arbitrarily well in polynomial time, unless P = NP. A special case of this observation solves an open problem by Rosenkrantz et al. [31]. We give a 2/3 approximation algorithm for one version of the geometric dispersion problem. This algorithm is strongly polynomial in the size of the input, i.e., its running time does not depend on the area of P . We also discuss extensions and open problems. Received October 1, 1998; revised September 17, 1999, and April 17, 2000.     

Application of the Feynman-Kac path integral method in finding excited states of quantum systems

Group theory considerations and properties of a continuous path are used to define a failure tree procedure for finding eigenvalues of the Schrödinger equation using stochastic methods. The procedure is used to calculate the lowest excited state eigenvalues of eigenfunctions possessing anti-symmetric nodal regions in configuration space using the Feynman-Kac path integral method. Within this method the solution of the imaginary time Schrödinger equation is approximated by random walk simulations on a discrete grid constrained only by symmetry considerations of the Hamiltonian. The required symmetry constraints on random walk simulations are associated with a given irreducible representation and are found by identifying the eigenvalues for the irreducible representation corresponding to symmetric or antisymmetric eigenfunctions for each group operator. The method provides exact eigenvalues of excited states in the limit of infinitesimal step size and infinite time. The numerical method is applied to compute the eigenvalues of the lowest excited states of the hydrogenic atom that transform as Γ² and Γ⁴ irreducible representations. Numerical results are compared with exact analytical results.     

Application of if-conversion to verification and optimization of workflows

Based on the workflow analysis graphs proposed in [1] and the well-known if-conversion method [2], a new algorithm of workflow verification is developed. This algorithm is based on the Boolean algebra principles, which is reflected in its name—Boolean Verification Algorithm (BVA). The BVA operates with arbitrary overlapping structures of the graph and with cycles. In the case of dense graphs, the time complexity of the algorithm does not exceed that of most other algorithms of workflow verification [3–6]. In the course of verification, the BVA determines an execution condition for each node of the graph, which makes it possible to create an additional algorithm of workflow optimization. Unlike the well-known algorithms of structural workflow optimization based on pattern transformations [7, 8], the proposed optimization algorithm allows for maximum (within a cycle) parallelization of workflows containing arbitrary overlapping structures.     

Generating certified code from formal proofs: a case study in homological algebra

We apply current theorem proving technology to certified code in the domain of abstract algebra. More concretely, based on a formal proof of the Basic Perturbation Lemma (a central result in homological algebra) in the prover Isabelle/HOL, we apply various code generation techniques, which lead to certified implementations of the associated algorithm in ML. In the formal proof, algebraic structures occurring in the Basic Perturbation Lemma are represented in a way, which is not directly amenable to code generation with the available tools. Interestingly, this representation is required in the proof, while for the algorithm simpler data structures are sufficient. Our approach is to establish a link between the non-executable setting of the proof and the executable representation in the algorithm, which is to be generated. This correspondence is established within the logical framework of Isabelle/HOL—that is, it is formally proved correct. The generated code is applied to and illustrated with a number of examples.     

A fast algorithm to compute irreducible and primitive polynomials in finite fields

In this paper we present a method to computeall the irreducible and primitive polynomials of degreem over the finite fieldGF(q). Our method finds each new irreducible or primitive polynomial with a complexity ofO(m) arithmetic operations inGF(q). The best previously known methods [3], [10] use the Berlekamp-Massey algorithm [7] and they have a complexityO(m ²). We reach mis improvement taking into account a systolic implementation [2] of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm.This work was supported in part by Spanish Grant CICYT TIC91-0472.     

Analysis of an upwind finite-difference scheme for a system of coupled singularly perturbed convection-diffusion equations

We study a system of coupled convection-diffusion equations. The equations have diffusion parameters of different magnitudes associated with them which give rise to boundary layers at either boundary. An upwind finite difference scheme on arbitrary meshes is used to solve the system numerically. A general error estimate is derived that allows to immediately conclude robust convergence – w.r.t. the perturbation parameters – for certain layer-adapted meshes, thus improving and generalising previous results [4]. We present the results of numerical experiments to illustrate our theoretical findings.     

Synthesis of continuous-valued logic functions defined in tabular form

The choice table provides one of the techniques for the representation of functions in continuous-valued logic [1]. The need to synthesize functions from choice tables arise in the design of hybrid [2] and analog [3] computers, and also in other applications of continuous-valued logic that are surveyed in [4]. The structure of the original table is determined by the external specification of the device or unit being designed. Algorithms are available for the synthesis of continuous-valued logic functions from choice tables of a special form, for instance, from ordered choice tables [ It is noted in [ that a general algorithm to synthesize a continuous-valued logic function from an arbitrary choice table is still unknown. In the present article, we derive a criterion that decides whether a given choice table defmes some continuous-valued logic function and construct a simple algorithm to synthesize the function from the table. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 42–49, March–April, 1998.