A solution to certain polynomial equations with applications to nonlinear fitting

We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in variables by reducing it to the problem of solving two special linear systems of size and rooting a single univariate polynomial of degree . Over , all solutions can be found with fixed precision using, up to polylogarithmic factors, bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to bit operations, up to polylogarithmic factors. As an application, we show how this can be used to fit data to a complex exponential sum with terms in the same, nearly optimal, time.

     

A finite element method for nearly incompressible elasticity problems

A finite element method is considered for dealing with nearly incompressible material. In the case of large deformations the nonlinear character of the volumetric contribution has to be taken into account. The proposed mixed method avoids volumetric locking also in this case and is robust for (with being the well-known Lamé constant). Error estimates for the -norm are crucial in the control of the nonlinear terms.

     

On the absolute Mahler measure of polynomials having all zeros in a sector. II

Let be an algebraic integer of degree , not or a root of unity, all of whose conjugates are confined to a sector . In the paper On the absolute Mahler measure of polynomials having all zeros in a sector, G. Rhin and C. Smyth compute the greatest lower bound of the absolute Mahler measure ( of , for belonging to nine subintervals of . In this paper, we improve the result to thirteen subintervals of and extend some existing subintervals.

     

Visible evidence for the Birch and Swinnerton-Dyer conjecture for modular abelian varieties of analytic rank zero

This paper provides evidence for the Birch and Swinnerton-Dyer conjecture for analytic rank  abelian varieties  that are optimal quotients of attached to newforms. We prove theorems about the ratio , develop tools for computing with , and gather data about certain arithmetic invariants of the nearly abelian varieties of level . Over half of these have analytic rank , and for these we compute upper and lower bounds on the conjectural order of  . We find that there are at least such for which the Birch and Swinnerton-Dyer conjecture implies that is divisible by an odd prime, and we prove for of these that the odd part of the conjectural order of really divides by constructing nontrivial elements of using visibility theory. We also give other evidence for the conjecture. The appendix, by Cremona and Mazur, fills in some gaps in the theoretical discussion in their paper on visibility of Shafarevich-Tate groups of elliptic curves.

     

Comparison theorems of Kolmogorov type and exact values of -widths on Hardy-Sobolev classes

Let be a strip in complex plane. denotes those -periodic, real-valued functions on which are analytic in the strip and satisfy the condition , . Osipenko and Wilderotter obtained the exact values of the Kolmogorov, linear, Gel'fand, and information -widths of in , , and 2-widths of in , , .

In this paper we continue their work. Firstly, we establish a comparison theorem of Kolmogorov type on , from which we get an inequality of Landau-Kolmogorov type. Secondly, we apply these results to determine the exact values of the Gel'fand -width of in , . Finally, we calculate the exact values of Kolmogorov -width, linear -width, and information -width of in , , .

     

On the modular curves

Let denote an elliptic curve over and the modular curve classifying the elliptic curves over such that the representations of in the 7-torsion points of and of are symplectically isomorphic. In case is given by a Weierstraß equation such that the invariant is a square, we exhibit here nontrivial points of . From this we deduce an infinite family of curves for which has at least four nontrivial points.

     

On the convergence of certain Gauss-type quadrature formulas for unbounded intervals

We consider the convergence of Gauss-type quadrature formulas for the integral , where is a weight function on the half line . The -point Gauss-type quadrature formulas are constructed such that they are exact in the set of Laurent polynomials }, where is a sequence of integers satisfying and . It is proved that under certain Carleman-type conditions for the weight and when or goes to , then convergence holds for all functions for which is integrable on . Some numerical experiments compare the convergence of these quadrature formulas with the convergence of the classical Gauss quadrature formulas for the half line.

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

Improved methods and starting values to solve the matrix equations iteratively

The two matrix iterations are known to converge linearly to a positive definite solution of the matrix equations , respectively, for known choices of and under certain restrictions on . The convergence for previously suggested starting matrices is generally very slow. This paper explores different initial choices of in both iterations that depend on the extreme singular values of and lead to much more rapid convergence. Further, the paper offers a new algorithm for solving the minus sign equation and explores mixed algorithms that use Newton's method in part.

     

Optimal logarithmic energy points on the unit sphere

We study minimum energy point charges on the unit sphere in , , that interact according to the logarithmic potential , where is the Euclidean distance between points. Such optimal -point configurations are uniformly distributed as . We quantify this result by estimating the spherical cap discrepancy of optimal energy configurations. The estimate is of order . Essential is an improvement of the lower bound of the optimal logarithmic energy which yields the second term in the asymptotical expansion of the optimal energy. Previously, this was known for the unit sphere in only. Furthermore, we present an upper bound for the error of integration for an equally-weighted numerical integration rule with the nodes forming an optimal logarithmic energy configuration. For polynomials of degree at most this bound is as . For continuous functions of satisfying a Lipschitz condition with constant the bound is as .

     

The global decay to discrete shocks for scalar monotone schemes

Given a family of discrete shocks of a monotone scheme, we prove that the discrete shock profile with rational shock speed is asymptotically stable with respect to the topology : if , then as under no restriction conditions of the initial data to the interval . The asymptotic wave profile is uniquely identified from the above family by a mass parameter.

     

A posteriori error estimates for general numerical methods for Hamilton-Jacobi equations. Part I: The steady state case

A new upper bound is provided for the L-norm of the difference between the viscosity solution of a model steady state Hamilton-Jacobi equation, , and any given approximation, . This upper bound is independent of the method used to compute the approximation ; it depends solely on the values that the residual takes on a subset of the domain which can be easily computed in terms of . Numerical experiments investigating the sharpness of the a posteriori error estimate are given.

     

Computations of Eisenstein series on Fuchsian groups

We present numerical investigations of the value distribution and distribution of Fourier coefficients of the Eisenstein series on arithmetic and non-arithmetic Fuchsian groups. Our numerics indicate a Gaussian limit value distribution for a real-valued rotation of as , and also, on non-arithmetic groups, a complex Gaussian limit distribution for when near and , at least if we allow at some rate. Furthermore, on non-arithmetic groups and for fixed with near , our numerics indicate a Gaussian limit distribution for the appropriately normalized Fourier coefficients.

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

Special prime numbers and discrete logs in finite prime fields

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

     

Extrapolation methods and derivatives of limits of sequences

Let be an infinite sequence whose limit or antilimit can be approximated very efficiently by applying a suitable extrapolation method E to . Assume that the and hence also are differentiable functions of some parameter , being the limit or antilimit of , and that we need to approximate . A direct way of achieving this would be by applying again a suitable extrapolation method E to the sequence , and this approach has often been used efficiently in various problems of practical importance. Unfortunately, as has been observed at least in some important cases, when and have essentially different asymptotic behaviors as , the approximations to produced by this approach, despite the fact that they are good, do not converge as quickly as those obtained for , and this is puzzling. In this paper we first give a rigorous mathematical explanation of this phenomenon for the cases in which E is the Richardson extrapolation process and E is a generalization of it, thus showing that the phenomenon has very little to do with numerics. Following that, we propose a procedure that amounts to first applying the extrapolation method E to and then differentiating the resulting approximations to , and we provide a thorough convergence and stability analysis in conjunction with the Richardson extrapolation process. It follows from this analysis that the new procedure for has practically the same convergence properties as E for . We show that a very efficient way of implementing the new procedure is by actually differentiating the recursion relations satisfied by the extrapolation method used, and we derive the necessary algorithm for the Richardson extrapolation process. We demonstrate the effectiveness of the new approach with numerical examples that also support the theory. We discuss the application of this approach to numerical integration in the presence of endpoint singularities. We also discuss briefly its application in conjunction with other extrapolation methods.

     

Littlewood polynomials with high order zeros

Let be the minimal length of a polynomial with coefficients divisible by . Byrnes noted that for each , and asked whether in fact . Boyd showed that for all , but . He further showed that , and that is one of the 5 numbers , or . Here we prove that . Similarly, let be the maximal power of dividing some polynomial of degree with coefficients. Boyd was able to find for . In this paper we determine for .