An efficient algorithm for the computation of Galois automorphisms

We describe an algorithm for computing the Galois automorphisms of a Galois extension which generalizes the algorithm of Acciaro and Klüners to the non-Abelian case. This is much faster in practice than algorithms based on LLL or factorization.

     

An adaptive algorithm for system level diagnosis

Consider a system of n units, at most t of which are faulty. An adaptive diagnosis algorithm is presented which uses a sequence of tests to identify a fault-free unit. The algorithm requires at most 2t − ν(t) tests, where ν(t) is the number of 1's in the binary representation of t. Moreover, many of the tests can be performed simultaneously. The previously best algorithms for the same purpose required 2t − 1 tests, none of which could be performed simultaneously.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

A space efficient algorithm for group structure computation

We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is (with denoting the group order), and we explicitly determine the -constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.

     

An algorithm for computing minimal curves

Let ?³ be the 3-dimensional projective space over an algebraically closed field K of characteristic 0, and R be the graded polynomial ring K[x ₀,x ₁,x ₂,x ₃]. If C is a curve of ?³, let M _c := ⊕ H ^l I _C (n) be its Hartshorne-Rao module: it is a graded R-module of finite length which, up to a shift in degrees, characterizes the biliaison class of C. M. Martin-Deschamps &; D. Perrin (Sur la classification des courbes gauches. Astérisque 184–185 (1990)) have proved that in every biliaison class of non arithmetically Cohen-Macaulay curves there exists a minimal curve, unique up to a deformation with constant cohomology and Hartshorne-Rao module, that is a curve C such that, if C ₁ is any curve in the biliaison class of C, then M _{C 1} = M _c(?n), with n ≧ 0. They have moreover given an algorithm for the computation of a minimal curve, based on the computation and the analysis of the minors of given orders of some submatrices of the second syzygy matrix σ ₂ of M. The aim of this paper is to give an improvement to the algorithm for computing a minimal curve of a given Hartshorne-Rao module. The key remark is that the information obtained from σ ₂ can analogously be obtained from the matrix f(σ ₂) with entries in the polynomial ring K[u], where f:R → K[u] is a map which evaluates the variables of R to random linear polynomials in K[u]. The advantage of this approach is first, that the computations are done in a simpler polynomial ring and second, that in K[u]|we can take advantage of the Smith Normal Form algorithm to analyze the structure of the minors of the given matrices. The algorithm is therefore probabilistic but rather efficient and allows to compute (the invariants of) a minimal curve associated to modules whose syzygies matrices are considerably large. The algorithms presented here have been partially implemented and tested in the computer algebra systems CoCoA, Maple and Macaulay.     

An algorithm for evolutionary surfaces

Summary An Algorithm is presented which allows to split the calculation of the mean curvature flow of surfaces with or without boundary into a series of Poisson problems on a series of surfaces. This gives a new method to solve Plateau's problem forH-surfaces.     

An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity

Kumar et al. consider the M/M/c/N+c feedback queue with constant retrial rate [1]. They provide a solution for the steady state probabilities based on the matrix-geometric method. We show that there exists a more efficient computation method to calculate the steady state probabilities when N+c$N+c$ is large. We prove that the number of zero-eigenvalues of the characteristic matrix polynomial associated with the balance equation is ⌊(N+c+2)/2⌋$\lfloor (N+c+2)/2\rfloor$. As consequence, the remaining eigenvalues inside the unit circle can be computed in a quick manner based on the Sturm sequences. Therefore, the steady state probabilities can be determined in an efficient way.     

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.     

An adaptive finite element algorithm with reliable and efficient error control for linear parabolic problems

An efficient and reliable a posteriori error estimate is derived for linear parabolic equations which does not depend on any regularity assumption on the underlying elliptic operator. An adaptive algorithm with variable time-step sizes and space meshes is proposed and studied which, at each time step, delays the mesh coarsening until the final iteration of the adaptive procedure, allowing only mesh and time-step size refinements before. It is proved that at each time step the adaptive algorithm is able to reduce the error indicators (and thus the error) below any given tolerance within a finite number of iteration steps. The key ingredient in the analysis is a new coarsening strategy. Numerical results are presented to show the competitive behavior of the proposed adaptive algorithm.

     

An efficient algorithm for voting sequences

The chaos theorems show that given almost any alternatives x and y, there exists voting sequence from x to y. However, proofs of such results have been purely existential; that is, there is no algorithm by which such a voting path can be constructed. In this paper, we present such an algorithm for one standard example. Furthermore, it is shown that the algorithm has the property that the voting sequence involves the fewest possible number of steps.     

An efficient algorithm for solving inequalities

An efficient algorithm for solving a finite system of inequalities in a finite number of iterations is described and analyzed.This work was supported by the UK Science and Engineering Research Council     

An efficient algorithm for enumeration of triangulations

We consider the problem of enumerating triangulations of n points in the plane in general position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation. It improves the previous bound by almost linear factor.     

An algorithm for the computation of the exponential spline

Summary Procedures for the calculation of the exponential spline (spline under tension) are presented in this paper. The procedureexsplcoeff calculates the second derivatives of the exponential spline. Using the second derivatives the exponential spline can be evaluated in a stable and efficient manner by the procedureexspl. The limiting cases of the exponential spline, the cubic spline and the linear spline are included. A proceduregenerator is proposed, which computes appropriate tension parameters. The performance of the algorithm is discussed for several examples.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

An algorithm for accelerated computation of DWTPer-based band preconditioners

We present a new algorithm for computing DWT-based preconditioners at a reduced cost, and we illustrate the savings that can be achieved with examples taken from the solution of a nonlinear problem by a Newton–Krylov method.     

An efficient computation of near-continuum rarefied gas flows

A numerical scheme for solving integral equations of rarefied gas dynamics is modified to provide more accurate results in the near continuum flows. The modified scheme is applied to the Poiseuille flow of a rarefied gas between parallel plates and in a cylindrical tube. Flow rate results obtained for both geometries are good over the complete range of Knudsen numbers. In particular, the results are found in excellent agreement with the analytic asymptotic formulas in the near continuum regime even when fairly low order of quadrature formulas are used.

---

Zusammenfassung Eine numerische Methode zur Lösung der Integralgleichung für die Dynamik verdünnter Gase wird modifiziert, um genauere Resultate nahe zur Kontinuumsgrenze zu liefern; sie wird für die Poiseuille-Strömung von verdünnten Gasen zwischen parallelen Platten und im zylindrischen Rohr angewendet. Die Resultate für die Durchlaßmenge sind über den ganzen Bereich der Knudsen-Zahlen gut. Die Ergebnisse sind in besonders guter Übereinstimmung mit den asymptotischen Formeln nahe zum Kontinuum-Regime, selbst wenn Quadraturformeln von eher niedrigem Grade verwendet werden.

     

An adaptive algorithm for discrete-time differential games

This paper presents an algorithm for a player to improve his performance by adapting optimally over his non-optimally playing opponent in discrete-time differential games. The algorithm first estimates the opponent's actual strategies and then constructs an adaptive strategy for the player. The adaptive strategy is periodically updated according to the opponent's behavior using the neighboring optimal closed-loop solution technique. An example is given which demonstrates the superiority of this algorithm over the conventional one which assumes that the opponent plays optimally.     

An adaptive search algorithm for numerical optimization

The flexible polyhedron (simplex) search algorithm is reviewed and some of its shortcomings highlighted. Particularly, the fixed search parameters are shown to be a sure liability and an improvement is proposed. A unidirectional optimal search algorithm is substituted for the set of fixed rules usually employed to modify the simplex. This modification proves especially effective in dealing with “narrow valley” situations, normally encountered whenever the decision variables exhibit some degree of correlation. The new adaptive algorithm compares well with the parent simplex method, featuring less function evaluations and better convergence properties in cases where the classical search techniques perform poorly or fail altogether.     

An efficient algorithm for maximal margin clustering

Maximal margin based frameworks have emerged as a powerful tool for supervised learning. The extension of these ideas to the unsupervised case, however, is problematic since the underlying optimization entails a discrete component. In this paper, we first study the computational complexity of maximal hard margin clustering and show that the hard margin clustering problem can be precisely solved in O(n ^d+2) time where n is the number of the data points and d is the dimensionality of the input data. However, since it is well known that many datasets commonly ‘express’ themselves primarily in far fewer dimensions, our interest is in evaluating if a careful use of dimensionality reduction can lead to practical and effective algorithms. We build upon these observations and propose a new algorithm that gradually increases the number of features used in the separation model in each iteration, and analyze the convergence properties of this scheme. We report on promising numerical experiments based on a ‘truncated’ version of this approach. Our experiments indicate that for a variety of datasets, good solutions equivalent to those from other existing techniques can be obtained in significantly less time.     

An efficient heuristic algorithm for minimum matching

We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asLN with (=0.3123±0.0016.

---

Zusammenfassung Wir stellen einen neuen heuristischen Algorithmus für minimale Matching-Probleme vor und wenden diesen auf das euklidische Problem mit zufÄlliger Punkteverteilung in 2 Dimensionen an. Auf Simulated Annealing basierend lÄuft der Algorithmus schneller als frühere heuristische Algorithmen und erreicht dabei suboptimale Lösungen gleich guter QualitÄt. Aus Konfigurationen mit bis zuN=20.000 Punkten im Einheitsquadrat schÄtzen wir, da\ für die LÄnge des minimalen Matchings asymptotischLN mit=0.3123±0.0016 gilt.

     

An efficient algorithm for the three-guard problem

Given a simple polygon P with two vertices u and v, the three-guard problem asks whether three guards can move from u to v such that the first and third guards are separately on two boundary chains of P from u to v and the second guard is always kept to be visible from two other guards inside P. It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from u to v and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in O(nlogn) time, and if so generate a walk in O(nlogn+m) time, where n denotes the number of vertices of P and the size of the optimal walk. This improves upon the previous time bounds O(n²) and O(n²logn), respectively. Moreover, our results can be used to solve other more sophisticated geometric problems.