Computing Modular Invariants of p-groups

Let V be a finite dimensional representation of a p -group, G, over a field,k , of characteristic p. We show that there exists a choice of basis and monomial order for which the ring of invariants, k [ V ]^G, has a finite SAGBI basis. We describe two algorithms for constructing a generating set for k [ V ] G. We use these methods to analyse k [2V₃ ]^U₃where U₃is the p -Sylow subgroup ofGL₃ (F_p) and 2 V₃is the sum of two copies of the canonical representation. We give a generating set for k [2 V₃]^U₃forp =  3 and prove that the invariants fail to be Cohen–Macaulay forp >  2. We also give a minimal generating set for k [mV₂ ]^Z / pwere V₂is the two-dimensional indecomposable representation of the cyclic group Z / p.     

Sample complexity of worst-case H-identification

We show that the sample complexity of qorst-case H^∞-identification is of order n², by proving that the minimal length of a fractional H^∞-cover for C_n, regarded as the linear space of complex-valued sequences of length n, is of order n². A unit vector u in ^∞ is a fractional H^∞-cover for C_n if for some

Full-size image

for all rh ε C_n, where is the z-transform of h. We also give similar results for real-valued sequences.     

Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

Lumped model of a non-linear distributed system by finite element method

The finite element method has been used to find an approximate lumped parameter model of a non-linear distributed parameter system. A one dimensional non-linear dispersion system is considered. The space domain is divided into a finite set of k elements. Each element, has n nodes. Within each element the concentration is represented by C(x,t)^(e) = [N][C] ^T where [N] = [n₁(x),n₂(x), [tdot] n_n(x)] and [C] = [C₁(t),C₂(t), [tdot] C_n(t)]. By using Galerkin's criterion a set of (k × n ? n+ 1) first order differential equations are obtained for C_i(t). These equations are solved by an iterative method. The concepts are illustrated by an example taking five three-node elements in the space domain. The results are compared with those obtained by a finite difference method. It is shown that the finite element method can be used effectively in modelling of a distributed system by a lumped system.     

Communication complexity of matrix computation over finite fields

We investigate the communication complexity of singularity testing in a finite field, where the problem is to determine whether a given square matrixM is singular. We show that, forn×n matrices whose entries are elements of a finite field of sizep, the communication complexity of this problem is (n ² logp). Our results imply tight bounds for several other problems likedetermining the rank andcomputing the determinant.This research was supported in part by NSF Grant CCR-8805978 and AFOSR Grant 87-0-400.     

Sieve algorithms for perfect power testing

A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x ^k . The usual algorithm to recognize perfect powers computes approximatekth roots forklog ₂ n, and runs in time O(log³ n log log logn).First we improve this worst-case running time toO(log³ n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC ² algorithm.Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log² n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log² n/log² logn) and a median running time ofO(logn).The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)^1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)^2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains.We also present computational results indicating that our sieve algorithms perform extremely well in practice.This work forms part of the second author's Ph.D. thesis at the University of Wisconsin-Madison, 1991. This research was sponsored by NSF Grants CCR-8552596 and CCR-8504485.     

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

Computing Stochastic Completion Fields in Linear-Time Using a Resolution Pyramid

We describe a linear-time algorithm for computing the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. Our algorithm is a resolution-pyramid-based method for solving a partial differential equation (PDE) characterizing a distribution of short, smooth completion shapes. The PDE consists of a set of independent advection equations in (x, y) coupled in the θ dimension by the diffusion equation. A previously described algorithm used a first-order, explicit finite difference scheme implemented on a rectangular grid. This algorithm required O(n³m) time for a grid of size n×n with m discrete orientations. Unfortunately, systematic error in solving the advection equations produced unwanted anisotropic smoothing in the (x, y) dimension. This resulted in visible artifacts in the completion fields. The amount of error and its dependence on θ have been previously characterized. We observe that by careful addition of extra spatial smoothing, the error can be made totally isotropic. The combined effect of this error and of intrinsic smoothness due to diffusion in the θ dimension is that the solution becomes smoother with increasing time, i.e., the high spatial frequencies drop out. By increasing Δx and Δt on a regular schedule, and using a second-order, implicit scheme for the diffusion term, it is possible to solve the modified PDE in O(n²m) time, i.e., time linear in the problem size. Using current hardware and for problems of typical size, this means that a solution which previously took 1 h to compute can now be computed in about 2 min.     

Numerical evaluation of Hankel transforms using Haar wavelets

The aim of the article is to find an efficient algorithm for local numerical evaluation of F _n (p) by expressing the corresponding finite Hankel transform [Fcirc] _n (p) in Haar series and truncating it.     

Constructing normalisers in finite soluble groups

This paper describes algorithms for constructing a Hall π-subgroup H of a finite soluble group G and the normaliser N_G(H). If G has composition length n, then H and N_G(H) can be constructed using O(n⁴ log |G|) and O(n⁵ log |G|) group multiplications, respectively. These algorithms may be used to construct other important subgroups such as Carter subgroups, system normalisers and relative system normalisers. Computer implementations of these algorithms can compute a Sylow 3-subgroup of a group with n = 84, and its normaliser in 47 seconds and 30 seconds, respectively. Constructing normalisers of arbitrary subgroups of a finite soluble group can be complicated. This is shown by an example where constructing a normaliser is equivalent to constructing a discrete logarithm in a finite field. However, there are no known polynomial algorithms for constructing discrete logarithms.     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Deciding the Vapnik–Červonenkis Dimension is∑p3-complete

N. Linialet al.raised the question of how difficult the computation of the Vapnik–Červonenkis dimension of a concept class over a finite universe is. C. Papadimitriou and M. Yannakakis obtained a first answer using matrix representations of concept classes. However, this approach does not capture classes having exponential size, like monomials, which are encountered in learning theory. We choose a more natural representation, which leads us to redefine the VC DIMENSION problem. We establish that VC DIMENSION is∑^p₃-complete, thereby giving a rare natural example of a∑^p₃-complete problem.     

Distributions having bases which generate finite dimensional Lie algebras

Let X¹,…, X^k be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TM_p. Then X¹,…, X^k form a local basis for a real analytic k-dimensional distribution x→D^k(x)=span{X¹(x),…,X^k(x)}. We study the question of when D^k admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X¹,…, X^k can often be greatly simplified.     

Bianchi-I cosmologies with magnetic and spinor fields

We consider Bianchi type I cosmologies with unidirectional magnetic and electric fields as well as a global spinor field ϕ(t) containing a nonlinearity in the form s ⁿ , where s = ϕ and n = const (the special case n = 1 corresponds to a Dirac massive field). The structure of the stress-energy tensor of the spinor field is shown to be the same as that of a perfect fluid with the equation of state p = wρ with the parameter w = n − 1. The Dirac massive spinor field and nonlinear fields with n < 4/3 are shown to be able to provide late-time isotropization. Talk given at the International Conference RUSGRAV-13, June 23–28, 2008, PFUR, Moscow.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Outer Interval Solution of the Eigenvalue Problem under General Form Parametric Dependencies

The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝ^n×n for the general case where the matrix elements a_ij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λ_μ, x^(μ)), μ = 1, ..., n, is suggested for the case where λ_μ is a simple eigenvalue. It is based on the use of an affine interval approximation of a_ij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real or complex eigenvalue, respectively.     

Constraint elimination method for the committee problem

We introduce a method of reducing the q-Member p-Committee Problem for an arbitrary finite system of sets to the same problem for a system of sets of smaller size and with a smaller number of subsystems with nonempty intersection maximal with respect to inclusion. For p = 1/2, for an infeasible system of linear inequalities in ℝ ⁿ we give an efficient implementation of this method with complexity polynomial in the number of inequalities and the number of committee elements, but exponential in the dimension of the space. For this implementation, we give experimental results for n = 2, 3.     

Wormholes supported by chiral fields

We consider static, spherically symmetric solutions of general relativity with a non-linear sigma model (NSM) as a source, i.e., a set of scalar fields Φ = (Φ¹, …, Φ ⁿ ) (so-called chiral fields) parametrizing a target space with a metric h _ab (Φ). For NSM with zero potential V (Φ), it is shown that the space-time geometry is the same as with a single scalar field but depends on h _ab . If the matrix h _ab is positive-definite, we obtain the Fisher metric, originally found for a canonical scalar field with positive kinetic energy; otherwise we obtain metrics corresponding to a phantom scalar field, including singular and nonsingular horizons (of infinite area) and wormholes. In particular, the Schwarzschild metric can correspond to a nontrivial chiral field configuration, which in this case has zero stress-energy. Some explicit examples of chiral field configurations are considered. Some qualitative properties of NSM configurations with nonzero potentials are pointed out.