Decomposition of algebras overF q (X 1,...,X m )

LetA be a finite dimensional associative algebra over the fieldF whereF is a finite (algebraic) extension of the function fieldF _q(X ₁,...,X _m). Here F_q denotes the finite field ofq elements (q=p^l for a primep). We address the problem of computing the Jacobson radical Rad (A) ofA and the problem of computing the minimal ideals of the radical-free part (Wedderburn decomposition). The algebraA is given by structure constants overF andF is given by structure constants overF _q(X ₁,...,X _m). We give algorithms to find these structural components ofA. Our methods run in polynomial time ifm is constant, in particular in the casem=1. The radical algorithm is deterministic. Our method for computing the Wedderburn decomposition ofA uses randomization (for factoring univariate polynomials overF _q).Research partially supported by Hungarian National Foundation for Scientific Research (OTKA), Grants 2581, F4116 and EC Cooperative Action IC 1000 (ALTEC).     

Properness and Inversion of Rational Parametrizations of Surfaces

 In this paper we characterize the properness of rational parametrizations of hypersurfaces by means of the existence of intersection points of some additional algebraic hypersurfaces directly generated from the parametrization over a field of rational functions. More precisely, if V is a hypersurface over an algebraically closed field ? of characteristic zero and is a rational parametrization of V, then the characterization is given in terms of the intersection points of the hypersurfaces defined by x _i q _i (tˉ)−p _i (tˉ), i=1,...,n over the algebraic closure of ?(V). In addition, for the case of surfaces we show how these results can be stated algorithmically. As a consequence we present an algorithmic criteria to decide whether a given rational parametrization is proper. Furthermore, if the parametrization is proper, the algorithm also computes the inverse of the parametrization. Moreover, for surfaces the auxiliary hypersurfaces turn to be plane curves over ?(V), and hence the algorithm is essentially based on resultants. We have implemented these ideas, and we have empirically compared our method with the method based on Gr?bner basis. Received: November 20, 2000; revised version: November 20, 2001     

Rank of a Hankel matrix over Z[x1,..., xr]

One of the main problems in the treatment of rational functions consists in representing them suitably for the purpose of their symbolic and algebraic manipulation. One can approach this problem by means of Hankel matrices if an efficient method for computing ranks is available. In this paper, a modular algorithm for determining the rank of a Hankel matrix with entries that are multivariate polynomials over the integers is presented. The algorithm is based on modular techniques, which consist in computing the rank of Hankel matrices over finite fields by a special algorithm that needsO(n²) arithmetic operations, wheren is the order of the matrix. The general solution is achieved by determining the maximum of the ranks computed over the finite fields.The worst case complexity of the algorithm isO(n^r+3G^r+n^r+2G^r+1) logn× log² L, whereG andL are some appropriate bounds for the degree and the norm of the entries respectively.Partially supported by A.I. Spain-Austria HU-007 and University of Alcala Project 92/39     

Closed form Laurent-Puiseux series of algebraic functions

There are several well-known algorithms to calculate the Puiseux series developments of the branches of an algebraic function. None of them, however, generates the series in closed form, even in those cases where such a formal result is available. They produce, instead, truncated series, and give information that can be used to handle the series as streams. Here we give a solution to the given problem. We combine an algorithm of D. V. and G. V. Chudnovsky that transforms the given algebraic equation into a differential equation for the function, and further into a recurrence equation for the Puiseux coefficients, with an algorithm of Koepf which in the case of hypergemetric type results in the formal series. A finite linear recurrence equation is optimal for a representation by streams. D. V. and G. V. Chudnovsky point out that their algorithm requires only0(M) field operations ifM is the order of the number of series terms considered. However, from a practical point of view, it is of importance that the complexity of the resulting recurrence equation — as well as of the differential equation — can be extremely high, a fact, which we illustrate by an example. It turns out, that many algebraic functions of low order with a sparse representation are of hypergeometric type, and so closed form representations for the corresponding series can be given.     

Lattice Structure and Linear Complexity of Nonlinear Pseudorandom Numbers

 It is shown that a q-periodic sequence over the finite field F _q passes an extended version of Marsaglia's lattice test for high dimensions if and only if its linear complexity is large. The consequences of this result for nonlinear and inversive pseudorandom number generators are worked out. Received: October 2, 2001 Keywords: Pseudorandom number generator, Nonlinear method, Inversive method, Linear complexity, Marsaglia's lattice test.     

Computing Cartan subalgebras of Lie algebras

We consider the algorithmic problem of computing Cartan subalgebras in Lie algebras over finite fields and algebraic number fields. We present a deterministic polynomial time algorithm for the case when the ground fieldk is sufficiently large. Our method is based on a solution of a linear algebra problem: the task of finding a locally regular element in a subspace of linear transformations. Also, we give a polynomial time algorithm for restricted Lie algebras over arbitrary finite fields. Both methods require an auxiliary procedure for finding non-nilpotent elements in subalgebras. This problem is also treated. Computational experiences are discussed at the end of the paper.Research supported in part by Hungarian National Foundation for Scientific Research grants T016503 and F4116     

A new efficient factorization algorithm for polynomials over small finite fields

We present a new deterministic factorization algorithm for polynomials over a finite prime fieldF _p . As in other factorization algorithms for polynomials over finite fields such as the Berlekamp algorithm, the key step is the linearization of the factorization problem, i.e., the reduction of the problem to a system of linear equations. The theoretical justification for our algorithm is based on a study of the differential equationy ^(p –1)+y ^p =0 of orderp–1 in the rational function fieldF _p(x). In the casep=2 the new algorithm is more efficient than the Berlekamp algorithm since there is no set-up cost for the coefficient matrix of the system of linear equations.     

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f : D ⁿ →F for subsets D⊂F. In particular, we prove an exponential lower bound on the complexity of depth 3 arithmetic circuits computing some explicit functions f:(F ^*) ⁿ →F (in particular, the determinant of a matrix). Received: July 7, 1998; revised version: January 13, 2000     

Formulas for series computations

We describe an algorithm that computes polynomials whose roots are the coefficients of any specific order of the Laurent series of a rational function. The algorithm uses only rational operations in the coefficient field of the function. This allows us to compute with the principal parts of the Laurent series, in particular with the residues of the function, without factoring or splitting its denominator. As applications, we get a generalisation of the residue formulas used in symbolic integration algorithms ton ^th-order formulas. We also get an algorithm that computes explicitly the principal parts at all the poles simultaneously, while computing in the field generated by the coefficients of the series instead of the one generated by the poles of the function. This yields an improved version of the necessary conditions for the various cases of Kovacic's algorithm, that expresses those conditions in the smallest possible extension field.     

Computing the irreducible real factors and components of an algebraic curve

We present algorithms that decompose an algebraic curve with rational coefficients in its defining bivariate equation into its irreducible real factors and its non-empty irreducible real components. We show that our algorithms are of polynomial bit complexity in the degree of the equation and the size of its coefficients. Our construction is based on computing the irreducible complex factors and then investigating high precision complex floating point coefficients of these factors and the complex norms.This material is based on work supported by the National Science Foundation under Grant No. CCR-87-05363 and under Grant No. CDA-8805910. A preliminary version of this paper appears in the Proceedings of the 5th Annual Symposium on Computational Geometry, ACM Press, pp. 79–87 (1989)     

On a robust and scalable linear elasticity solver based on a saddle point formulation

This paper presents a newly developed iterative algorithm for solving problems of linear isotropic elasticity discretized by means of mixed finite elements. It continues work started in References 1–5. The proposed method uses a pressure Schur complement approach to solve a saddle‐point system arising in the mixed formulation. As an inner solver for the displacement field variables it uses an extension to the robust black‐box multilevel procedure suggested in Reference 4. The proposed method works on a hierarchical sequence of finite element meshes to solve the problem with an arithmetic cost, nearly proportional to the dimension of the arising algebraic system. The coarsest mesh in the above sequence of meshes can consist of almost arbitrary triangular patches, which allows in practice to capture the solution even using a moderate number of successive refinement steps. The rate of convergence of the algorithm is bounded uniformly with respect to the problem coefficients, namely the Young's modulus E and the Poisson ratio ν. This makes it possible to apply the method for a broad class of engineering problems. Copyright © 1999 John Wiley & Sons, Ltd.     

Explicit factorization ofx^{2^k } + 1 overF p with primep≡3 mod 4

In this note we give a complete explicit factorization of + 1 into irreducible polynomials overF _p for a primep3 mod 4. As a result we can construct an irreducible polynomial overF _p of degree of any power of 2. Some interesting properties of the coefficients of the irreducibles are noted. We also mention that our results may be useful in applying the Fast Fourier Transform over finite fields.     

Decomposition of ordinary differential polynomials

In this paper, we present a complete algorithm to decompose nonlinear differential polynomials in one variable and with coefficients in a computable differential field of characteristic zero. The algorithm provides an efficient reduction of the problem to the factorization of LODOs over the same coefficient field. Besides arithmetic operations, the algorithm needs decomposition of algebraic polynomials, factorization of multi-variable polynomials, and solution of algebraic linear equation systems. The algorithm is implemented in Maple for the constant field case. The program can be used to decompose differential polynomials with thousands of terms effectively. This article was partially supported by a National Key Basic Research Project of China (NO. G1998030600) and by a USA NSF grant CCR-0201253.     

A fast algorithm for expansion over spherical harmonics

Algorithms for expansion over spherical harmonics are often used in electrostatic field calculation, calculation of the density functions in quantum chemistry and calculation of molecular surfaces. It usually includes expansion over spherical harmonics of degrees to several dozens. The usual method is to use an integration method over some grid on the unit sphere and in fact is a multiplication of the matrix of values of spherical harmonics in the grid points by a vector of values of the expanding function in the set of points. This algorithm executes O(NL²) operations whereN is the number of the grid points andL is the maximal degree of the spherical harmonics involved. We provide an algorithm of complexity O(NLlog² L) for multiplication of the matrix of values of spherical harmonics in points of an arbitrary grid on the unit sphere. The algorithm is based on interrelation between spherical harmonics and Legendre polynomials and on a fast algorithm for expansion over Legendre polynomials.     

Computing Parametric Geometric Resolutions

 Given a polynomial system of n equations in n unknowns that depends on some parameters, we define the notion of parametric geometric resolution as a means to represent some generic solutions in terms of the parameters. The coefficients of this resolution are rational functions of the parameters; we first show that their degree is bounded by the Bézout number d ⁿ , where d is a bound on the degrees of the input system. Then we present a probabilistic algorithm to compute a parametric resolution. Its complexity is polynomial in the size of the output and in the complexity of evaluation of the input system. The probability of success is controlled by a quantity polynomial in the Bézout number. We present several applications of this process, notably to computa- tions in the Jacobian of hyperelliptic curves and to questions of real geometry. Received: July 5, 2001; revised version: September 5, 2002 Key words: Polynomial systems with parameters, Complexity, Theory of elimination, Symbolic Newton operator.     

Hyperelliptic curves with reduced automorphism group A 5

We study genus g hyperelliptic curves with reduced automorphism group A ₅ and give equations y ² = f(x) for such curves in both cases where f(x) is a decomposable polynomial in x ² or x ⁵. For any fixed genus the locus of such curves is a rational variety. We show that for every point in this locus the field of moduli is a field of definition. Moreover, there exists a rational model y ² = F(x) or y ² = x F(x) of the curve over its field of moduli where F(x) can be chosen to be decomposable in x ² or x ⁵. While similar equations have been given in (Bujalance et al. in Mm. Soc. Math. Fr. No. 86, 2001) over , this is the first time that these equations are given over the field of moduli of the curve.     

Robust and efficient domain decomposition preconditioners for adaptive hp finite element approximations of linear elasticity with and without discontinuous coefficients

Adaptive finite element methods (FEM) generate linear equation systems that require dynamic and irregular patterns of storage, access, and computation, making their parallelization difficult. Additional difficulties are generated for problems in which the coefficients of the governing partial differential equations have large discontinuities. We describe in this paper the development of a set of iterative substructuring based solvers and domain decomposition preconditioners with an algebraic coarse‐grid component that address these difficulties for adaptive hp approximations of linear elasticity with both homogeneous and inhomogeneous material properties. Our solvers are robust and efficient and place no restrictions on the mesh or partitioning. Copyright © 2003 John Wiley & Sons, Ltd.     

The complexity of routing in hierarchical PNNI networks

We study the complexity of computing a route in a hierarchical PNNI network, with H levels of hierarchy, in which N nodes are grouped into clusters at each level. We determine cluster sizes that minimize an upper bound on the total time for all the path computations required to compute a route. Our model casts the problem as a nonlinear convex optimization problem, and employs nonlinear duality theory. We derive explicit closed form upper bounds on the minimum total path computation time, as a function of N, for H=2 and H=3, and show how the upper bound, and the optimal cluster sizes, can be computed for any H. We provide a conjecture on the complexity of PNNI routing for any H, and use this conjecture to determine the limit of the complexity as H→∞. We also prove that the minimum total path computation time is a non-increasing function of H. Our results provide counterexamples to a claim by Van Mieghem that a related top-down hierarchical routing method has lower computational complexity.     

On liouvillian solutions of linear differential equations

This paper deals with the problem of finding liouvillian solutions of a homogeneous linear differential equationL(y)=0 of ordern with coefficients in a differential fieldk. For second order linear differential equations with coefficients ink _o(x), wherek _o is a finite algebraic extension ofQ, such an algorithm has been given by J. Kovacic and implemented. A general decision procedure for finding liouvillian solutions of a differential equation of ordern has been given by M.F. Singer, but the resulting algorithm, although constructive, is not in implementable form even for second order equations. Both algorithms use the fact that, ifL(y)=0 has a liouvillian solution, then,L(y)=0 has a solutionz such thatu=z/z is algebraic overk. Using the action of the differential galois group onu and the theory of projective representation we get sharp bounds (n) for the algebraic degree ofu for differential equations of arbitrary ordern. For second order differential equations we get the bound (2)=12 used in the algorithm of J. Kovacic and for third order differential equation we improve the bound given by M.F. Singer from 360 to (3)36. We also show that not all values less than or equal to (n) are possible values for the algebraic degree ofu. For second order differential equations we rediscover the values 2, 4, 6, and 12 used in the Kovacic Algorithm and for third order differential equations we get the possibilities 3,4, 6, 7, 9, 12, 21, and 36. We prove that if the differential Galois group ofL(y)=0 is a primitive unimodular linear group, then all liouvillian solutions are algebraic. From this it follows that, if a third order differential equationL(y)=0 is not of Fuchsian type, then the logarithmic derivative of some liouvillian solution ofL(y)=0 is algebraic of degree 3. We also derive an upper bound for the minimal numberN(n) of possible degreesm of the minimal polynomial of an algebraic solution of the riccati equation associated withL(y)=0.Supported by Deutsche Forschungsgemeinschaft while visiting North Carolina State University     

A note on the moments of Kloosterman sums

It is well known that Kloosterman sums have many important applications in many subjects, such as finding the roots of an equation over finite fields or the rational points on an algebraic curve, determining the weight distributions of some algebraic geometric codes, calculating some exponential sums in number theory etc. We provide some new identities and results on the moments of Kloosterman sums.