An algebraic multigrid method for high order time-discretizations of the div-grad and the curl-curl equations

We present an algebraic multigrid algorithm for fully coupled implicit Runge–Kutta and Boundary Value Method time-discretizations of the div-grad and curl-curl equations. The algorithm uses a blocksmoother and a multigrid hierarchy derived from the hierarchy built by any algebraic multigrid algorithm for the stationary version of the problem. By a theoretical analysis and numerical experiments, we show that the convergence is similar to or better than the convergence of the scalar algebraic multigrid algorithm on which it is based. The algorithm benefits from several possibilities for implementation optimization. This results in a computational complexity which, for a modest number of stages, scales almost linearly as a function of the number of variables.     

A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function

In this paper we present a refined version of the Newton polygon process to compute the Puiseux expansions of an algebraic function defined over the rational function field. We determine an upper bound for the bit-complexity of computing the singular part of a Puiseux expansion by this algorithm, and use a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions to show that this computational complexity is polynomial in the degrees and the logarithm of the height of the polynomial defining the algebraic function.

     

A lifting and recombination algorithm for rational factorization of sparse polynomials

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.     

The algebraic regulator problem from the state-space point of view

We study the algebraic aspects of the regulator problem, using some new ideas in the state-space (“geometric”) approach to feedback design problems for linear multi- variable systems. Necessary and sufficient conditions are given for the solvability of a general version of this problem, requiring output stability, internal stability, and disturbance decoupling as well. An algorithm is given by which these conditions can be verified from the system parameters.     

An algorithm for testing Leopoldt's conjecture

Based on an elementary version of Leopoldt's conjecture due to Iwasawa and Sands we develop an algorithm for testing this conjecture in an arbitrary algebraic number field for any prime p. Using this algorithm we are able to prove Leopoldt's conjecture for several pure fields of degree 5 and 7. We also discuss relations with class numbers.     

Minimal average degree aberration and the state polytope for experimental designs

For a particular experimental design, there is interest in finding which polynomial models can be identified in the usual regression set up. The algebraic methods based on Gröbner bases provide a systematic way of doing this. The algebraic method does not, in general, produce all estimable models but it can be shown that it yields models which have minimal average degree in a well-defined sense and in both a weighted and unweighted version. This provides an alternative measure to that based on “aberration” and moreover is applicable to any experimental design. A simple algorithm is given and bounds are derived for the criteria, which may be used to give asymptotic Nyquist-like estimability rates as model and sample sizes increase.     

The Computation of Invariant Fields and a Constructive Version of a Theorem by Rosenlicht

Let G be an algebraic group acting on an irreducible variety X. We present an algorithm for computing the invariant field k(X)^G. Moreover, we give a constructive version of a theorem of Rosenlicht, which says that almost all orbits can be separated by rational invariants. More precisely, we give an algorithm for computing a nonempty open subset of X with a geometric quotient.     

Mixing Microworld and Cas Features in Building Computer Systems that Help Students Learn Algebra

We present the design principles for a new kind of computer system that helps students learn algebra. The fundamental idea is to have a system based on the microworld paradigm that allows students to make their own calculations, as they do with paper and pencil, without being obliged to use commands, and to verify the correctness of these calculations. This requires an advanced editor for algebraic expressions, an editor for algebraic reasoning and an algorithm that calculates the equivalence of two algebraic expressions. A second feature typical of microworlds is the ability to provide students information about the state of the problem in order to help them move toward a solution. A third feature comes from the CAS (Computer Algebra System) paradigm, consisting of providing commands for executing certain algebraic actions; these commands have to be adapted to the current level of understanding of the students in order to only present calculations they can do without difficulty. With this feature, such a computer system can provide an introduction to the proper use of a Computer Algebra System. We have implemented most of these features in a computer system called aplusix for a sub-domain of algebra, and we have done several experiments with students (mainly grades 9 and 10). We had good results, with positive feedback from students and teachers. aplusix is currently a prototype that can be downloaded from http://aplusix.imag.fr. It will become a commercial product during 2004. This revised version was published online in July 2006 with corrections to the Cover Date.     

Cubature formulas on a sphere invariant under the icosahedral rotation group

An algorithm is proposed for constructing cubature formulas on a sphere that are invariant under the icosahedral rotation group. The algorithm is applied to construct new cubature formulas of algebraic order of accuracy n = 19, 20, 21, 23, 24, 25. Parameters of these cubature formulas are given to 16 significant digits. A table, which containsmain characteristics of all optimal cubature formulas for the icosahedral rotation group exact to order 35, is included. A real version of F. Klein’s formula, which establishes a connection between basic invariant forms of the icosahedral rotation group, is presented.     

The theory of the exponential differential equations of semiabelian varieties

The complete first-order theories of the exponential differential equations of semiabelian varieties are given. It is shown that these theories also arise from an amalgamation-with-predimension construction in the style of Hrushovski. The theories include necessary and sufficient conditions for a system of equations to have a solution. The necessary conditions generalize Ax’s differential fields version of Schanuel’s conjecture to semiabelian varieties. There is a purely algebraic corollary, the “Weak CIT” for semiabelian varieties, which concerns the intersections of algebraic subgroups with algebraic varieties.     

Addendum to “Connesʼ embedding conjecture and sums of hermitian squares” [Adv. Math. 217 (4) (2008) 1816–1837]

We show that Connes? embedding conjecture (CEC) is equivalent to a real version of the same (RCEC). Moreover, we show that RCEC is equivalent to a real, purely algebraic statement concerning trace positive polynomials. This purely algebraic reformulation of CEC had previously been given in both a real and a complex version in a paper of the last two authors. The second author discovered a gap in this earlier proof of the equivalence of CEC to the real algebraic reformulation (the proof of the complex algebraic reformulation being correct). In this note, we show that this gap can be filled with help of the theory of real von Neumann algebras.     

A two‐grid SA‐AMG convergence bound that improves when increasing the polynomial degree

In this paper, we consider the convergence rate of a smoothed aggregation algebraic multigrid method, which uses a simple polynomial (1 ? t)^ν or an optimal Chebyshev‐like polynomial to construct the smoother and prolongation operator. The result is purely algebraic, whereas a required main weak approximation property of the tentative interpolation operator is verified for a spectral element agglomeration version of the method. More specifically, we prove that, for partial differential equations (PDEs), the two‐grid method converges uniformly without any regularity assumptions. Moreover, the convergence rate improves uniformly when the degree of the polynomials used for the smoother and the prolongation increases. Such a result, as is well‐known, would imply uniform convergence of the multilevel W‐cycle version of the algorithm. Numerical results, for both PDE and non‐PDE (graph Laplacian) problems are presented to illustrate the theoretical findings. Published 2016. This article is a U.S. Government work and is in the public domain in the USA.     

Linearity-preserving flux correction and convergence acceleration for constrained Galerkin schemes

This paper is concerned with the development of general-purpose algebraic flux correction schemes for continuous (linear and multilinear) finite elements. In order to enforce the discrete maximum principle (DMP), we modify the standard Galerkin discretization of a scalar transport equation by adding diffusive and antidiffusive fluxes. The result is a nonlinear algebraic system satisfying the DMP constraint. An estimate based on variational gradient recovery leads to a linearity-preserving limiter for the difference between the function values at two neighboring nodes. A fully multidimensional version of this scheme is obtained by taking the sum of local bounds and constraining the total flux. This new approach to algebraic flux correction provides a unified treatment of stationary and time-dependent problems. Moreover, the same algorithm is used to limit convective fluxes, anisotropic diffusion operators, and the antidiffusive part of the consistent mass matrix.The nonlinear algebraic system associated with the constrained Galerkin scheme is solved using fixed-point defect correction or a nonlinear SSOR method. A dramatic improvement of nonlinear convergence rates is achieved with the technique known as Anderson acceleration (or Anderson mixing). It blends a number of last iterates in a GMRES fashion, which results in a Broyden-like quasi-Newton update. The numerical behavior of the proposed algorithms is illustrated by a grid convergence study for convection-dominated transport problems and anisotropic diffusion equations in 2D.     

The algebraic degree of geometric optimization problems

In this paper we apply Galois methods to certain fundamentalgeometric optimization problems whose exact computational complexity has been an open problem for a long time. In particular we show that the classic Weber problem, along with theline-restricted Weber problem and itsthree-dimensional version are in general not solvable by radicals over the field of rationals. One direct consequence of these results is that for these geometric optimization problems there existsno exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction ofkth roots. This leaves only numerical or symbolic approximations to the solutions, where the complexity of the approximations is shown to be primarily a function of the algebraic degree of the optimum solution point.     

SECOND-ORDER BOOLEAN ALGEBRAS

Opgedra aan Prof. Hennie Schutte by geleentheid van sy sestigste verjaarsdag.

Abstract

A Boolean algebra is the algebraic version of a field of sets. The complex algebra C(B) of a Boolean algebra B is defined over the power set of B; it is a field of sets with extra operations. The notion of a second-order Boolean algebra is intended to be the algebraic version of the complex algebra of a Boolean algebra. To this end a representation theorem is proved.     

An Algebraic Analogue of Exel–Pardo C∗-Algebras

Algebras and Representation Theory - We introduce an algebraic version of the Katsura C?-algebra of a pair A,B of integer matrices and an algebraic version of the Exel–Pardo...     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

Two variations of a theorem of Kronecker

We present two variations of Kronecker's classical result that every nonzero algebraic integer that lies with its conjugates in the closed unit disc is a root of unity. The first is an analogue for algebraic nonintegers, while the second is a several variable version of the result, valid over any field.