bluuebunny/crossref_metadata_2025 huggingface dataset:
𝐿-functions and class numbers of imaginary quadratic fields and of quadratic extensions of an imaginary quadratic field
Authors: Louboutin Stéphane
Published: June 2010

Starting from the analytic class number formula involving its L-function, we first give an expression for the class number of an imaginary quadratic field which, in the case of large discriminants, provides us with a much more powerful numerical technique than that of counting the number of reduced definite positive binary quadratic forms, as has been used by Buell in order to compute his class number tables. Then, using class field theory, we will construct a periodic character

χ
\chi

, defined on the ring of integers of a field K that is a quadratic extension of a principal imaginary quadratic field k, such that the zeta function of K is the product of the zeta function of k and of the L-function

L
(
s
,
χ
)

L(s,\chi )

. We will then determine an integral representation of this L-function that enables us to calculate the class number of K numerically, as soon as its regulator is known. It will also provide us with an upper bound for these class numbers, showing that Hua’s bound for the class numbers of imaginary and real quadratic fields is not the best that one could expect. We give statistical results concerning the class numbers of the first 50000 quadratic extensions of

Q

(
i
)

{\mathbf {Q}}(i)

with prime relative discriminant (and with K/Q a non-Galois quartic extension). Our analytic calculation improves the algebraic calculation used by Lakein in the same way as the analytic calculation of the class numbers of real quadratic fields made by Williams and Broere improved the algebraic calculation consisting in counting the number of cycles of reduced ideals. Finally, we give upper bounds for class numbers of K that is a quadratic extension of an imaginary quadratic field k which is no longer assumed to be of class number one.
A method of tabulating the number-theoretic function 𝑔(𝑘)
Authors: Scheidler Renate , Williams Hugh C.
Published: June 2010

Let

g
(
k
)

g(k)

be the least integer

>
k
+
1

> k + 1

such that all prime factors of

(

g
(
k
)

k

)

\left ( {\begin {array}{*{20}{c}} {g(k)} \\ k \\ \end {array} } \right )

are greater than k. The function

g
(
k
)

g(k)

appears to show quite irregular behavior and is hard to compute. This paper describes a method of computing

g
(
k
)

g(k)

, using sieving techniques, and provides a table of values of

g
(
k
)

g(k)

for

k
≤
140

k \leq 140

.
Error analysis of 𝑄𝑅 updating with exponential windowing
Authors: Stewart G. W.
Published: June 2010

Exponential windowing is a widely used technique for suppressing the effects of old data as new data is added to a matrix. Specifically, given an

n
×
p

n \times p

matrix

X
n

{X_n}

and a "forgetting factor"

β
∈
(
0
,
1
)

\beta \in (0,1)

, one works with the matrix

diag

(

β

n
−
1

,

β

n
−
2

,
…
,
1
)

X
n

{\operatorname {diag}}({\beta ^{n - 1}},{\beta ^{n - 2}}, \ldots ,1){X_n}

. In this paper we examine an updating algorithm for computing the QR factorization of

diag

(

β

n
−
1

,

β

n
−
2

,
…
,
1
)

X
n

{\operatorname {diag}}({\beta ^{n - 1}},{\beta ^{n - 2}}, \ldots ,1){X_n}

and show that it is unconditionally stable in the presence of rounding errors.
Improvement of Nakamula’s upper bound for the absolute discriminant of a sextic number field with two real conjugates
Authors: Stroeker R. J.
Published: June 2010

Let K be the compositum of a real quadratic number field

K

2

{{\mathbf {K}}_2}

and a complex cubic number field

K

3

{{\mathbf {K}}_3}

. Further, let

ε
\varepsilon

be a unit of K which is also a relative unit with respect to

K

/

K

2

{\mathbf {K}}/{{\mathbf {K}}_2}

and

K

/

K

3

{\mathbf {K}}/{{\mathbf {K}}_3}

. The absolute discriminant of this non-Galois sextic number field K is estimated from above by a simple, strictly increasing, polynomial function of

ε
\varepsilon

. This estimate, which can be used to determine a generator for the cyclic group of relative units, substantially improves a similar bound due to Nakamula. The method employed makes nontrivial use of computer algebra techniques.
The accuracy of cell vertex finite volume methods on quadrilateral meshes
Authors: Süli Endre
Published: June 2010

For linear first-order hyperbolic equations in two dimensions we restate the cell vertex finite volume scheme as a finite element method. On structured meshes consisting of distorted quadrilaterals, the global error is shown to be of second order in various mesh-dependent norms, provided that the quadrilaterals are close to parallelograms in the sense that the distance between the midpoints of the diagonals is of the same order as the measure of the quadrilateral. On tensor product nonuniform meshes, the cell vertex scheme coincides with the familiar box scheme. In this case, second-order accuracy is shown without any additional assumption on the regularity of the mesh, which explains the insensitivity of the cell vertex scheme to mesh stretching in the coordinate directions, observed in practice.
A preconditioned GMRES method for nonsymmetric or indefinite problems
Authors: Xu Jinchao , Cai Xiao-Chuan
Published: June 2010

A preconditioning technique is proposed for nonsymmetric or indefinite linear systems of equations. The main idea in our theory, roughly speaking, is first to use some "coarser mesh" space to correct the nonpositive portion of the eigenvalues of the underlying operator and then switch to use a symmetric positive definite preconditioner. The generality of our theory allows us to apply any known preconditioners that were orginally designed for symmetric positive definite problems to nonsymmetric or indefinite problems, without losing the optimality that the original one has. Some numerical experiments based on GMRES are reported.
Variable-stepsize explicit two-step Runge-Kutta methods
Authors: Jackiewicz Z. , Zennaro M.
Published: June 2010

Variable-step explicit two-step Runge-Kutta methods for the numerical solution of ordinary differential equations are studied. Order conditions are derived and the results about the minimal number of stages required to attain a given order are established up to order five. The existence of embedded pairs of continuous Runge-Kutta methods and two-step Runge-Kutta methods of order

p
−
1

p - 1

and p is proved. This makes it possible to estimate local discretization error of continuous Runge-Kutta methods without any extra evaluations of the right-hand side of the differential equation. An algorithm to construct such embedded pairs is described, and examples of (3, 4) and (4, 5) pairs are presented. Numerical experiments illustrate that local error estimation of continuous Runge-Kutta methods based on two-step Runge-Kutta methods appears to be almost as reliable as error estimation by Richardson extrapolation, at the same time being much more efficient.
On real quadratic fields of class number two
Authors: Mollin R. A. , Williams H. C.
Published: June 2010

It is the primary purpose of the paper to determine all real quadratic fields

Q
(

d

)

Q(\sqrt d )

of class number

h
(
d
)
=
2

h(d) = 2

when

k
≤
24

k \leq 24

(with one possible exception). Here, k is the period length of the continued fraction expansion of either

ω
=

d

\omega = \sqrt d

, in the case

d
≡
2

d \equiv 2

or 3

(
mod

4
)

\pmod 4

, or of

ω
=
(
1
+

d

)

/

2

\omega = (1 + \sqrt d )/2

, in the case

d
≡
1

(
mod

4
)

d \equiv 1\, \pmod 4

.
Explicit canonical methods for Hamiltonian systems
Authors: Okunbor Daniel , Skeel Robert D.
Published: June 2010

We consider canonical partitioned Runge-Kutta methods for separable Hamiltonians

H
=
T
(
p
)
+
V
(
q
)

H = T(p) + V(q)

and canonical Runge-Kutta-Nyström methods for Hamiltonians of the form

H
=

1
2

p

T

M

−
1

p
+
V
(
q
)

H = \frac {1}{2}{p^{\text {T}}}{M^{ - 1}}p + V(q)

with M a diagonal matrix. We show that for explicit methods there is great simplification in their structure. Canonical methods of orders one through four are constructed. Numerical experiments indicate the suitability of canonical numerical schemes for long-time integrations.
Presentations for unit groups of modular group algebras of groups of order 16
Authors: Sandling Robert
Published: June 2010

For a p-group G and the field F of p elements, let V denote the group of normalized units of the group algebra FG. Generators and relations are provided for V for each group G of order dividing 16. The presentations are sufficiently concise to permit transcription for machine calculation with V. Some applications are described. A theoretical method for obtaining presentations for V is developed. It is most effective when

p
=
2

p = 2

, or when

p
=
3

p = 3

and the commutator subgroup G’ is of order 3. Implementation involves extensive calculation in FG.
Quadratic fields with special class groups
Authors: Solderitsch James J.
Published: June 2010

For every prime number

p
≥
5

p \geq 5

it is shown that, under certain hypotheses on

x
∈

Q

x \in {\mathbf {Q}}

, the imaginary quadratic fields

Q

(

x

2
p

−
6

x
p

+
1

)

{\mathbf {Q}}(\sqrt {{x^{2p}} - 6{x^p} + 1} )

have ideal class groups with noncyclic p-parts. Several numerical examples with

p
=
5

p = 5

and 7 are presented. These include the field
\[

Q

(

−
4805446123032518648268510536

)
.

{\mathbf {Q}}(\sqrt { - 4805446123032518648268510536} ).

\]
The 7-part of its class group is isomorphic to

C
(
7
)
×
C
(
7
)
×
C
(
7
)

C(7) \times C(7) \times C(7)

, where

C
(
n
)

C(n)

denotes a cyclic group of order n.
Linear finite element methods for planar linear elasticity
Authors: Brenner Susanne C. , Sung Li-Yeng
Published: June 2010

A linear nonconforming (conforming) displacement finite element method for the pure displacement (pure traction) problem in two-dimensional linear elasticity for a homogeneous isotropic elastic material is considered. In the case of a convex polygonal configuration domain,

O

(
h
)

(

O

(

h
2

)
)

\mathcal {O}(h)\;(\mathcal {O}({h^2}))

error estimates in the energy

(

L
2

)

({L^2})

norm are obtained. The convergence rate does not deteriorate for nearly incompressible material. Furthermore, the convergence analysis does not rely on the theory of saddle point problems.
Algebraic methods for modified orthogonal polynomials
Authors: Galant David
Published: June 2010

Some algebraic methods are given to implement Uvarov’s extended Christoffel theorem. The stability of the algorithms is discussed.
Termination conditions for approximating linear problems with noisy information
Authors: Kacewicz B. Z. , Plaskota L.
Published: June 2010

We study the diameter termination criterion for approximating linear continuous problems. It is assumed that only nonexact information about the problem is available. We evaluate the quality of the diameter termination criterion by comparing it with the theoretically best stopping condition. The comparison is made with respect to the cost of computing an

ϵ
\epsilon

-approximation. Although the diameter termination criterion is independent of a particular problem, it turns out to be essentially equivalent to the theoretical condition. Optimal information and the best way of constructing an

ϵ
\epsilon

-approximation are exhibited.
Convergence of a finite element method for the drift-diffusion semiconductor device equations: the zero diffusion case
Authors: Cockburn Bernardo , Triandaf Ioana
Published: June 2010

In this paper a new explicit finite element method for numerically solving the drift-diffusion semiconductor device equations is introduced and analyzed. The method uses a mixed finite element method for the approximation of the electric field. A finite element method using discontinuous finite elements is used to approximate the concentrations, which may display strong gradients. The use of discontinuous finite elements renders the scheme for the concentrations trivially conservative and fully parallelizable. In this paper we carry out the analysis of the model method (which employs a continuous piecewise-linear approximation to the electric field and a piecewise-constant approximation to the electron concentration) in a model problem, namely, the so-called unipolar case with the diffusion terms neglected. The resulting system of equations is equivalent to a conservation law whose flux, the electric field, depends globally on the solution, the concentration of electrons. By exploiting the similarities of this system with classical scalar conservation laws, the techniques to analyze the monotone schemes for conservation laws are adapted to the analysis of the new scheme. The scheme, considered as a scheme for the electron concentration, is shown to satisfy a maximum principle and to be total variation bounded. Its convergence to the unique weak solution is proven. Numerical experiments displaying the performance of the scheme are shown.
The density of zeros of forms for which weak approximation fails
Authors: Heath-Brown D. R.
Published: June 2010

The weak approximation principle fails for the forms

x
3

+

y
3

+

z
3

=
k

w
3

{x^3} + {y^3} + {z^3} = k{w^3}

, when

k
=
2

k = 2

or 3. The question therefore arises as to what asymptotic density one should predict for the rational zeros of these forms. Evidence, both numerical and theoretical, is presented, which suggests that, for forms of the above type, the product of the local densities still gives the correct global density.
Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems
Authors: Li T. Y. , Zeng Zhong Gang
Published: June 2010

The eigenvalues of a matrix A are the zeros of its characteristic polynomial
\[

f
(
λ
)
=
det
[
A
−
λ
I
]
.

f(\lambda ) = \det [A - \lambda I].

\]
With Hyman’s method of determinant evaluation, a new homotopy continuation method, homotopy-determinant method, is developed in this paper for finding all eigenvalues of a real upper Hessenberg matrix. In contrast to other homotopy continuation methods, the homotopy-determinant method calculates eigenvalues without computing their corresponding eigenvectors. Like all homotopy methods, our method solves the eigenvalue problem by following eigen-value paths of a real homotopy whose regularity is established to the extent necessary. The inevitable bifurcation and possible path jumping are handled by effective processes. The numerical results of our algorithm, and a comparison with its counterpart, subroutine HQR in EISPACK, are presented for upper Hessenberg matrices of numerous dimensions, with randomly generated entries. Although the main advantage of our method lies in its natural parallelism, the numerical results show our algorithm to be strongly competitive also in serial mode.
Finding suitable curves for the elliptic curve method of factorization
Authors: Atkin A. O. L. , Morain F.
Published: June 2010

Using the parametrizations of Kubert, we show how to produce infinite families of elliptic curves which have prescribed nontrivial torsion over Q and rank at least one. These curves can be used to speed up the ECM factorization algorithm of Lenstra. We also briefly discuss curves with complex multiplication in this context.
Iterative schemes for nonsymmetric and indefinite elliptic boundary value problems
Authors: Bramble James H. , Leyk Zbigniew , Pasciak Joseph E.
Published: June 2010

The purpose of this paper is twofold. The first is to describe some simple and robust iterative schemes for nonsymmetric and indefinite elliptic boundary value problems. The schemes are based in the Sobolev space

H
1

(
Ω
)

{H^1}(\Omega )

and require minimal hypotheses. The second is to develop algorithms utilizing a coarse-grid approximation. This leads to iteration matrices whose eigenvalues lie in the right half of the complex plane. In fact, for symmetric indefinite problems, the iteration is reduced to a well-conditioned symmetric positive definite system which can be solved by conjugate gradient iteration. Applications of the general theory as well as numerical examples are given.
Some gamma function inequalities
Authors: Alzer Horst
Published: June 2010

A class of completely monotonic functions are presented involving the gamma function as well as the derivative of the psi function. As a consequence, new upper and lower bounds for the ratio

Γ
(
x
+
1
)

/

Γ
(
x
+
s
)

\Gamma (x + 1)/\Gamma (x + s)

are obtained and compared with related bounds given in part by J. D. Kečkić and P. M. Vasić. Our results are further applied to obtain functions which are Laplace transforms of infinitely divisible probability measures.
On the Euclidean nature of four cyclic cubic fields
Authors: Godwin H. J. , Smith J. R.
Published: June 2010

It is shown that the cyclic cubic fields with discriminants

103
2

,

109
2

,

127
2

{103^2},{109^2},{127^2}

, and

157
2

{157^2}

are Euclidean
Substructure preconditioners for elliptic saddle point problems
Authors: Rusten Torgeir , Winther Ragnar
Published: June 2010

Domain decomposition preconditioners for the linear systems arising from mixed finite element discretizations of second-order elliptic boundary value problems are proposed. The preconditioners are based on subproblems with either Neumann or Dirichlet boundary conditions on the interior boundary. The preconditioned systems have the same structure as the nonpreconditioned systems. In particular, we shall derive a preconditioned system with conditioning independent of the mesh parameter h. The application of the minimum residual method to the preconditioned systems is also discussed.
On the use of Lagrange multipliers in domain decomposition for solving elliptic problems
Authors: Swann Howard
Published: June 2010

The primal hybrid method for solving second-order elliptic equations is extended from finite element approximations to general bases. Variational techniques are used to show convergence of approximations to the solution of the homogeneous Dirichlet problem for selfadjoint equations. Error estimates are obtained and examples are given.
Analysis of a robust finite element approximation for a parabolic equation with rough boundary data
Authors: French Donald A. , King J. Thomas
Published: June 2010

The approximation of parabolic equations with nonhomogeneous Dirichlet boundary data by a numerical method that consists of finite elements for the space discretization and the backward Euler time discretization is studied. The boundary values are assumed in a least squares sense. It is shown that this method achieves an optimal rate of convergence for rough (only

L
2

{L^2}

) boundary data and for smooth data as well. The results of numerical computations which confirm the robust theoretical error estimates are also presented.
The Monte Carlo complexity of Fredholm integral equations
Authors: Heinrich Stefan , Mathé Peter
Published: June 2010

A complexity study of Monte Carlo methods for Fredholm integral equations is carried out. We analyze the problem of computing a functional

μ
(
y
)

\mu (y)

, where y is the solution of a Fredholm integral equation
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="y left-parenthesis s right-parenthesis equals integral Underscript upper I Superscript m Baseline Endscripts k left-parenthesis s comma t right-parenthesis y left-parenthesis t right-parenthesis d t plus f left-parenthesis s right-parenthesis comma s element-of upper I Superscript m Baseline">

y
(
s
)
=

∫

I
m

k
(
s
,
t
)
y
(
t
)

d
t
+
f
(
s
)
,

s
∈

I
m

y(s) = \int _{{I^m}} {k(s,t)y(t)\;dt + f(s),\quad s \in {I^m}}

\]
, on the m-dimensional unit cube

I
m

{I^m}

, where the kernel k and right-hand side f are given r times differentiable functions. We permit stochastic numerical methods which can make use of function evaluations of k and f only. All Monte Carlo methods known to the authors for solving the above problem are of the order

n

−
1

/

2

{n^{ - 1/2}}

, while the optimal deterministic methods yield rate

n

−
r

/

(
2
m
)

{n^{ - r/(2m)}}

, thus taking into account the given smoothness of the data. Here, n denotes the (average) number of function evaluations performed. The optimal algorithm we present combines deterministic and stochastic methods in an optimal way. It can be seen that both rates—the standard Monte Carlo rate for general continuous data and the deterministic rate for r-smooth data—multiply. This provides the smallest error that stochastic methods of given computational cost can achieve.
Counting points on elliptic curves over 𝐅_{2^{𝐦}}
Authors: Menezes Alfred J. , Vanstone Scott A. , Zuccherato Robert J.
Published: June 2010

In this paper we present an implementation of Schoof’s algorithm for computing the number of

F

2
m

{F_{{2^m}}}

-points of an elliptic curve that is defined over the finite field

F

2
m

{F_{{2^m}}}

. We have implemented some heuristic improvements, and give running times for various problem instances.
Spherical designs, discrepancy and numerical integration
Authors: Grabner Peter J. , Tichy Robert F.
Published: June 2010

A spherical design is a point configuration on the sphere, which yields exact equal-weight quadrature formulae for polynomials up to a given degree. Until now only very specific constructions for spherical designs are known. We establish connections to spherical cap discrepancy and show some general discrepancy bounds. Furthermore, we reformulate the problem of constructing designs as an optimization problem and develop an algorithm for finding ’practical designs’.
On the minimal elements for the sequence of all powers in the Lemoine-Kátai algorithm
Authors: Pihko Jukka
Published: June 2010

It is proved, with the help of a computer, that form=20m = 20the firstmminimal elements for the sequence of all powers in an integer-representing algorithm are given by<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="y Subscript i Baseline equals i comma i equals 1 comma 2 comma 3 comma y Subscript i plus 1 Baseline equals left-parenthesis y Subscript i Superscript 2 Baseline plus 6 y Subscript i Baseline plus 1 right-parenthesis slash 4 comma i equals 3 comma ellipsis comma m minus 1">yi=i,i=1,2,3,yi+1=(yi2+6yi+1)/4,i=3,…,m−1{y_i} = i,i = 1,2,3,{y_{i + 1}} = (y_i^2 + 6{y_i} + 1)/4,i = 3, \ldots ,m - 1. This extends an earlier result of the author (form=10m = 10).
On the use of reducible polynomials as random number generators
Authors: Wang Da Kai , Compagner Aaldert
Published: June 2010

The randomness properties and the hierarchy of correlation coefficients are studied of approximate-maximum-length sequences, for which the characteristic polynomial is a product of several primitive polynomials. The randomness properties are almost the same as for maximum-length sequences characterized by a primitive polynomial with many terms and of the same degree. Reducible characteristic polynomials have acceptable figures of merit and can be of extremely high degree. Since they are also easily constructed and implemented, reducible polynomials are strong candidates for reliable random number generation, especially at the bit rates needed in large-scale Monte Carlo simulations.
Modified FFTs for fused multiply-add architectures
Authors: Linzer Elliot , Feig Ephraim
Published: June 2010

We introduce fast Fourier transform algorithms (FFTs) designed for fused multiply-add architectures. We show how to compute a complex discrete Fourier transform (DFT) of lengthn=2mn = {2^m}with83nm−169n+2−29(−1)m\frac {8}{3}nm - \frac {{16}}{9}n + 2 - \frac {2}{9}{( - 1)^m}real multiply-adds. For real input, this algorithm uses43nm−179n+3−19(−1)m\frac {4}{3}nm - \frac {{17}}{9}n + 3 - \frac {1}{9}{( - 1)^m}real multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of ann×nn \times narray of complex data using143n2m−43n2−49n(−1)m+169\frac {{14}}{3}{n^2}m - \frac {4}{3}{n^2} - \frac {4}{9}n{( - 1)^m} + \frac {{16}}{9}real multiply-adds. For each problem studied, the number of multiply-adds that our algorithms use is a record upper bound for the number required.
On the rate of convergence of the nonlinear Galerkin methods
Authors: Devulder Christophe , Marion Martine , Titi Edriss S.
Published: June 2010

In this paper we provide estimates to the rate of convergence of the nonlinear Galerkin approximation method. In particular, and by means of an illustrative example, we show that the nonlinear Galerkin method converges faster than the usual Galerkin method.
Solving real polynomial systems with real homotopies
Authors: Li T. Y. , Wang Xiao Shen
Published: June 2010

When a real homotopy is used for solving a polynomial system with real coefficients, bifurcation of some of the homotopy paths at singular points is inevitable. The main result of this paper shows that, generically, the solution set of a real homotopy contains no singular point other than a finite number of quadratic turning points. At a quadratic turning point, the bifurcation phenomenon is quite simple. It consists of two bifurcation branches with their tangent vectors being perpendicular to each other.
Parabolic approximations of the convection-diffusion equation
Authors: Lohéac J.-P. , Nataf F. , Schatzman M.
Published: June 2010

We propose an approximation of the convection-diffusion operator which consists in the product of two parabolic operators. This approximation is much easier to solve than the full convection-diffusion equation, which is elliptic in space. We prove that this approximation is of order three in the viscosity and that the classical parabolic approximation is of order one in the viscosity. Numerical examples are given to demonstrate the effectiveness of our new approximation.
Small two-variable exponential Diophantine equations
Authors: Styer Robert
Published: June 2010

We examine exponential Diophantine equations of the form

a

b
x

=
c

d
y

+
e

a{b^x} = c{d^y} + e

. Consider

a
≤
50

a \leq 50

,

c
≤
50

c \leq 50

,

|

e

|

≤
1000

|e|\; \leq 1000

, and b and d from the set of primes 2, 3, 5, 7, 11, and 13. Our work proves that no equation with parameters in these ranges can have solutions with

x
>
18

x > 18

. Our algorithm formalizes and extends a method used by Guy, Lacampagne, and Selfridge in 1987.
A parallel algorithm for computing the eigenvalues of a symmetric tridiagonal matrix
Authors: Swarztrauber Paul N.
Published: June 2010

A parallel algorithm, called polysection, is presented for computing the eigenvalues of a symmetric tridiagonal matrix. The method is based on a quadratic recurrence in which the characteristic polynomial is constructed on a binary tree from polynomials whose degree doubles at each level. Intervals that contain exactly one zero are determined by the zeros of polynomials at the previous level which ensures that different processors compute different zeros. The signs of the polynomials at the interval endpoints are determined a priori and used to guarantee that all zeros are found. The use of finite-precision arithmetic may result in multiple zeros; however, in this case, the intervals coalesce and their number determines exactly the multiplicity of the zero. For an

N
×
N

N \times N

matrix the eigenvalues can be determined in

O
(

log
2

N
)

O({\log ^2}N)

time with

N
2

{N^2}

processors and

O
(
N
)

O(N)

time with N processors. The method is compared with a parallel variant of bisection that requires

O
(

N
2

)

O({N^2})

time on a single processor,

O
(
N
)

O(N)

time with N processors, and

O
(
log
⁡
N
)

O(\log N)

time with

N
2

{N^2}

processors.
New estimates for multilevel algorithms including the 𝑉-cycle
Authors: Bramble James H. , Pasciak Joseph E.
Published: June 2010

The purpose of this paper is to provide new estimates for certain multilevel algorithms. In particular, we are concerned with the simple additive multilevel algorithm discussed recently together with J. Xu and the standard V-cycle algorithm with one smoothing step per grid. We shall prove that these algorithms have a uniform reduction per iteration independent of the mesh sizes and number of levels, even on nonconvex domains which do not provide full elliptic regularity. For example, the theory applies to the standard multigrid V-cycle on the L-shaped domain, or a domain with a crack, and yields a uniform convergence rate. We also prove uniform convergence rates for the multigrid V-cycle for problems with nonuniformly refined meshes. Finally, we give a new multigrid approach for problems on domains with curved boundaries and prove a uniform rate of convergence for the corresponding multigrid V-cycle algorithms.
Stability of the discretized pantograph differential equation
Authors: Buhmann Martin , Iserles Arieh
Published: June 2010

In this paper we study discretizations of the general pantograph equation
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="y prime left-parenthesis t right-parenthesis equals a y left-parenthesis t right-parenthesis plus b y left-parenthesis theta left-parenthesis t right-parenthesis right-parenthesis plus c y prime left-parenthesis phi left-parenthesis t right-parenthesis right-parenthesis comma t greater-than-or-equal-to 0 comma y left-parenthesis 0 right-parenthesis equals y 0 comma">

y
′

(
t
)
=
a
y
(
t
)
+
b
y
(
θ
(
t
)
)
+
c

y
′

(
ϕ
(
t
)
)
,

t
≥
0
,

y
(
0
)
=

y
0

,

y’(t) = ay(t) + by(\theta (t)) + cy’(\phi (t)),\quad t \geq 0,\quad y(0) = {y_0},

\]
, where a, b, c, and

y
0

{y_0}

are complex numbers and where

θ
\theta

and

ϕ
\phi

are strictly increasing functions on the nonnegative reals with

θ
(
0
)
=
ϕ
(
0
)
=
0

\theta (0) = \phi (0) = 0

and

θ
(
t
)
>
t
,
ϕ
(
t
)
>
t

\theta (t) > t, \phi (t) > t

for positive t. Our purpose is an analysis of the stability of the numerical solution with trapezoidal rule discretizations, and we will identify conditions on a, b, c and the stepsize which imply that the solution sequence

{

y
n

}

n
=
0

∞

\{ {y_n}\} _{n=0}^\infty

is bounded or that it tends to zero algebraically, as a negative power of n.
The minimum discriminant of totally real algebraic number fields of degree 9 with cubic subfields
Authors: Fujita Hiroyuki
Published: June 2010

With the help of the computer language UBASIC86, the minimum discriminant

d
(
K
)

d(K)

of totally real algebraic number fields K of degree 9 with cubic subfields F is determined. It is given by

d
(
K
)
=
16240385609

d(K) = 16240385609

. The defining equation for K is given by
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis x right-parenthesis equals x Superscript 9 Baseline minus x Superscript 8 Baseline minus 9 x Superscript 7 Baseline plus 4 x Superscript 6 Baseline plus 26 x Superscript 5 Baseline minus 2 x Superscript 4 Baseline minus 25 x cubed minus x squared plus 7 x plus 1">

f
(
x
)
=

x
9

−

x
8

−
9

x
7

+
4

x
6

+
26

x
5

−
2

x
4

−
25

x
3

−

x
2

+
7
x
+
1

f(x) = {x^9} - {x^8} - 9{x^7} + 4{x^6} + 26{x^5} - 2{x^4} - 25{x^3} - {x^2} + 7x + 1

, and K is uniquely determined by

d
(
K
)

d(K)

up to Q-isomorphism. The field K has the cubic subfield F with

d
(
F
)
=
49

d(F) = 49

defined by the polynomial

f
(
x
)
=

x
3

+

x
2

−
2
x
−
1

f(x) = {x^3} + {x^2} - 2x - 1

.
Polynomial invariants of 2-bridge knots through 22 crossings
Authors: Kanenobu Taizo , Sumi Toshio
Published: June 2010

We calculate the homfly, Kauffman, Jones, Q, and Conway polynomials of 2-bridge knots through 22 crossings and list all the pairs sharing the same polynomial invariants.
Chebyshev expansions for modified Struve and related functions
Authors: MacLeod Allan J.
Published: June 2010

We consider the approximation of the modified Struve functions

L

0

{{\mathbf {L}}_0}

and

L

1

{{\mathbf {L}}_1}

, and the related functions

I
0

−

L

0

{I_0} - {{\mathbf {L}}_0}

and

I
1

−

L

1

{I_1} - {{\mathbf {L}}_1}

, where

I
0

,

I
1

{I_0},{I_1}

are modified Bessel functions. Chebyshev expansions are derived to an accuracy of 20D for these functions. By using generalized bilinear and biquadratic maps we optimize the number of coefficients for 20D accuracy.
Some necessary conditions for convergence of the GBDF methods
Authors: Suleiman Mohamed Bin
Published: June 2010

The Generalized Backward Differentiation methods for solving stiff higher-order ordinary differential equations are described. The convergence, zero stability and consistency of these methods are defined. Next, the zero stability and consistency conditions necessary for convergence are proven. The order for which the methods are zero stable is also determined.
Partitioned Runge-Kutta methods for separable Hamiltonian problems
Authors: Abia L. , Sanz-Serna J. M.
Published: June 2010

Separable Hamiltonian systems of differential equations have the form

d

p

/

d
t
=
−
∂
H

/

∂

q

d{\mathbf {p}}/dt = - \partial H/\partial {\mathbf {q}}

,

d

q

/

d
t
=
∂
H

/

∂

p

d{\mathbf {q}}/dt = \partial H/\partial {\mathbf {p}}

, with a Hamiltonian function H that satisfies

H
=
T
(

p

)
+
V
(

q

)

H = T({\mathbf {p}}) + V({\mathbf {q}})

(T and V are respectively the kinetic and potential energies). We study the integration of these systems by means of partitioned Runge-Kutta methods, i.e., by means of methods where different Runge-Kutta tableaux are used for the p and q equations. We derive a sufficient and "almost" necessary condition for a partitioned Runge-Kutta method to be canonical, i.e., to conserve the symplectic structure of phase space, thereby reproducing the qualitative properties of the Hamiltonian dynamics. We show that the requirement of canonicity operates as a simplifying assumption for the study of the order conditions of the method.
Squares in quadratic progression
Authors: Pinch R. G. E.
Published: June 2010

The sequence of consecutive integer squares has constant second difference 2. We list every such sequence of squares containing a term less than

1000
2

{1000^2}

.
Runge-Kutta methods and local uniform grid refinement
Authors: Trompert R. A. , Verwer J. G.
Published: June 2010

Local uniform grid refinement (LUGR) is an adaptive grid technique for computing solutions of partial differential equations possessing sharp spatial transitions. Using nested, finer-and-finer uniform subgrids, the LUGR technique refines the space grid locally around these transitions, so as to avoid discretization on a very fine grid covering the entire physical domain. This paper examines the LUGR technique for time-dependent problems when combined with static regridding. Static regridding means that in the course of the time evolution, the space grid is adapted at discrete times. The present paper considers the general class of Runge-Kutta methods for the numerical time integration. Following the method of lines approach, we develop a mathematical framework for the general Runge-Kutta LUGR method applied to multispace-dimensional problems. We hereby focus on parabolic problems, but a considerable part of the examination applies to hyperbolic problems as well. Much attention is paid to the local error analysis. The central issue here is a "refinement condition" which is to underly the refinement strategy. By obeying this condition, spatial interpolation errors are controlled in a manner that the spatial accuracy obtained is comparable to the spatial accuracy on the finest grid if this grid would be used without any adaptation. A diagonally implicit Runge-Kutta method is discussed for illustration purposes, both theoretically and numerically.
The cusp forms of weight 3 on Γ₂(2,4,8)
Authors: van Geemen Bert , van Straten Duco
Published: June 2010

The congruence subgroup

Γ
2

(
2
,
4
,
8
)

{\Gamma _2}(2,4,8)

of the group

Γ
2

{\Gamma _2}

of

4
×
4

4 \times 4

integral symplectic matrices is contained in

Γ
2

(
4
)

{\Gamma _2}(4)

and contains

Γ
2

(
8
)

{\Gamma _2}(8)

, with

Γ
2

(
n
)

{\Gamma _2}(n)

the principal congruence subgroup of level n. The Satake compactification of the quotient of the three-dimensional Siegel upper half space by

Γ
2

(
2
,
4
,
8
)

{\Gamma _2}(2,4,8)

is shown to be a complete intersection of ten quadrics in

P

13

{\mathbb {P}^{13}}

. We determine the space of global holomorphic three forms on this space, which coincides with the space of cusp forms of weight 3 on

Γ
2

(
2
,
4
,
8
)

{\Gamma _2}(2,4,8)

; it has dimension 2283. Finally, we study the action of the Hecke operators on this space and consider the Andrianov L-functions of some eigenforms.
A 𝐵₂-sequence with larger reciprocal sum
Authors: Zhang Zhen Xiang
Published: June 2010

A sequence of positive integers is called a

B
2

{B_2}

-sequence if the pairwise differences are all distinct. The Mian-Chowla sequence is the

B
2

{B_2}

-sequence obtained by the greedy algorithm. Its reciprocal sum

S
∗

{S^\ast }

has been conjectured to be the maximum over all

B
2

{B_2}

-sequences. In this paper we give a

B
2

{B_2}

-sequence which disproves this conjecture. Our sequence is obtained as follows: the first 14 terms are obtained by the greedy algorithm, the 15th term is 229, from the 16th term on, the greedy algorithm continues. The reciprocal sum of the first 300 terms of our sequence is larger than

S
∗

{S^\ast }

.
On a problem of Erdős concerning primitive sequences
Authors: Zhang Zhen Xiang
Published: June 2010

A sequence

A
=
{

a
i

}

A = \{ {a_i}\}

of positive integers

a
1

>

a
2

>
⋯

{a_1} > {a_2} > \cdots

is said to be primitive if no term of A divides any other. Let

Ω
(
a
)

\Omega (a)

denote the number of prime factors of a counted with multiplicity. Let

p
(
a
)

p(a)

denote the least prime factor of a and

A
(
p
)

A(p)

denote the set of

a
∈
A

a \in A

with

p
(
a
)
=
p

p(a) = p

. The set

A
(
p
)

A(p)

is called homogeneous if there is some integer

s
p

{s_p}

such that either

A
(
p
)
=
∅

A(p) = \emptyset

or

Ω
(
a
)
=

s
p

\Omega (a) = {s_p}

for all

a
∈
A
(
p
)

a \in A(p)

. Clearly, if

A
(
p
)

A(p)

is homogeneous, then

A
(
p
)

A(p)

is primitive. The main result of this paper is that if A is a positive integer sequence such that

1
∉
A

1 \notin A

and each

A
(
p
)

A(p)

is homogeneous, then
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation Underscript a less-than-or-equal-to n comma a element-of upper A Endscripts StartFraction 1 Over a log a EndFraction less-than-or-equal-to sigma-summation Underscript p less-than-or-equal-to n comma p prime Endscripts StartFraction 1 Over p log p EndFraction for n greater-than 1 period">

∑

a
≤
n
,
a
∈
A

1

a
log
⁡
a

≤

∑

p
≤
n
,
p

prime

1

p
log
⁡
p

for

n
>
1.

\sum \limits _{a \leq n,a \in A} {\frac {1}{{a\log a}} \leq } \sum \limits _{p \leq n,p\;{\text {prime}}} {\frac {1}{{p\log p}}} \quad {\text {for}}\;n > 1.

\]
This would then partially settle a question of Erdős who asked if this inequality holds for any primitive sequence A.
An extension of the Lehmers’ picturesque exponential sums
Authors: Apostol Tom M.
Published: June 2010

A class of exponential sums studied by D. H. Lehmer and Emma Lehmer is generalized by replacing a root of unity by an arbitrary complex number x.
Three points of great height on elliptic curves
Authors: Bremner Andrew , Buell Duncan A.
Published: June 2010

We give three elliptic curves whose generators have great height, demonstrating along the way a moderately efficient method for finding such points.
A refinement of H. C. Williams’ 𝑞th root algorithm
Authors: Williams Kenneth S. , Hardy Kenneth
Published: June 2010

Let p and q be primes such that

p
≡
1

(
mod

q
)

p \equiv 1 \pmod q

. Let a be an integer such that

a

(
p
−
1
)

/

q

≡
1

(
mod

p
)

{a^{(p - 1)/q}} \equiv 1 \pmod p

. In 1972, H. C. Williams gave an algorithm which determines a solution of the congruence

x
q

≡
a

(
mod

p
)

{x^q} \equiv a \pmod p

in

O
(

q
3

log
⁡
p
)

O({q^3}\log p)

steps, once an integer b has been found such that

(

b
q

−
a

)

(
p
−
1
)

/

q

≢

0
,
1

(
mod

p
)

{({b^q} - a)^{(p - 1)/q}} \nequiv 0,1 \pmod p

. A step is an arithmetic operation

(
mod

p
)

\pmod p

or an arithmetic operation on q-bit integers. We present a refinement of this algorithm which determines a solution in

O
(

q
4

)
+
O
(

q
2

log
⁡
p
)

O({q^4}) + O({q^2}\log p)

steps, once b has been determined. Thus the new algorithm is better when q is small compared with p.
The factorization of the ninth Fermat number
Authors: Lenstra A. K. , Lenstra H. W. , Manasse M. S. , Pollard J. M.
Published: June 2010

In this paper we exhibit the full prime factorization of the ninth Fermat numberF9=2512+1{F_9} = {2^{512}} + 1. It is the product of three prime factors that have 7, 49, and 99 decimal digits. We found the two largest prime factors by means of the number field sieve, which is a factoring algorithm that depends on arithmetic in an algebraic number field. In the present case, the number field used wasQ(25){\mathbf {Q}}(\sqrt [5]{2}). The calculations were done on approximately 700 workstations scattered around the world, and in one of the final stages a supercomputer was used. The entire factorization took four months.
Uniform interior error estimates for the Reissner-Mindlin plate model
Authors: Gastaldi Lucia
Published: June 2010

Interior error estimates are derived for the solution of the Reissner-Mindlin plate model discretized by mixed-interpolated elements. Precisely, it is shown that the error in an interior domain can be estimated by the sum of two terms: the first has the best order of accuracy that is possible locally for the finite element spaces used, the second is a weak norm of the error on a slightly larger domain (this term measures the effects from outside of this domain). The analysis is based on some abstract properties enjoyed by the finite element spaces considered.
Lattice rules by component scaling
Authors: Lyness J. N. , Sørevik T.
Published: June 2010

We introduce a theory of rectangular scaling of integer lattices. This may be used to construct families of lattices. We determine the relation between the Zaremba index

ρ
(
Λ
)

\rho (\Lambda )

of various members of the same family. It appears that if one member of a family has a high index, some of the other family members of higher order may have extraordinarily high indices. We have applied a technique based on this theory to lists of good lattices available to us. This has enabled us to construct lists of excellent previously unknown lattices of high order in three and four dimensions and of moderate order in five dimensions.
A search for aliquot cycles and amicable pairs
Authors: Moews David , Moews Paul C.
Published: June 2010

A search for aliquot cycles below

3.6
⋅

10

10

3.6 \cdot {10^{10}}

and amicable pairs below

10

11

{10^{11}}

is described. Three new cycles of length 4 and one new cycle of length 6 are exhibited. Four triples of amicable pairs with the same pair-sum are also exhibited.
A conjecture in addition chains related to Scholz’s conjecture
Authors: Aiello Walter , Subbarao M. V.
Published: June 2010

Let

l
(
n
)

l(n)

denote, as usual, the length of a shortest addition chain for a given positive integer n. The most famous unsolved problem in addition chains is Scholz’s 1937 conjecture that for all natural numbers

n
,
l
(

2
n

−
1
)
≤
l
(
n
)
+
n
−
1

n,l({2^n} - 1) \leq l(n) + n - 1

. While this conjecture has been proved for certain classes of values of n, its validity for all n is yet an open problem. In this paper, we put forth a new conjecture, namely, that for each integer

n
≥
1

n \geq 1

there exists an addition chain for

2
n

−
1

{2^n} - 1

whose length equals

l
(
n
)
+
n
−
1

l(n) + n - 1

. Obviously, our conjecture implies (and is stronger than) Scholtz’s conjecture. However, it is not as bold as conjecturing that

l
(

2
n

−
1
)
=
l
(
n
)
+
n
−
1

l({2^n} - 1) = l(n) + n - 1

, which is known to hold, so far, for only the twenty-one values of n which were obtained by Knuth and Thurber after extensive computations. By utilizing a series of algorithms we establish our conjecture for all

n
≤
128

n \leq 128

by actually computing the desired addition chains. We also show that our conjecture holds for infinitely many n, for example, for all n which are powers of 2.
Zaremba’s conjecture and sums of the divisor function
Authors: Cusick T. W.
Published: June 2010

Zaremba conjectured that given any integer

m
>
1

m > 1

, there exists an integer

a
>
m

a > m

with a relatively prime to m such that the simple continued fraction

[
0
,

c
1

,
…
,

c
r

]

[0,{c_1}, \ldots ,{c_r}]

for a/m has

c
i

≤
B

{c_i} \leq B

for

i
=
1
,
2
…
,
r

i = 1,2 \ldots ,r

, where B is a small absolute constant (say

B
=
5

B = 5

). Zaremba was only able to prove an estimate of the form

c
i

≤
C
log
⁡
m

{c_i} \leq C\log m

for an absolute constant C. His first proof only applied to the case where m is a prime; later he gave a very much more complicated proof for the case of composite m. Building upon some earlier work which implies Zaremba’s estimate in the case of prime m, the present paper gives a much simpler proof of the corresponding estimate for composite m.
On the cuspidal spectrum of the arithmetic Hecke groups
Authors: Knopp Marvin I.
Published: June 2010

Let

Γ
(

m

)

(
m
=
1
,
2
,
3
)

\Gamma (\sqrt m )\;(m = 1,2,3)

be the three arithmetic Hecke groups, generated by the translation

z
↦
z
+

m

z \mapsto z + \sqrt m

and the inversion

z
↦
−

1
z

z \mapsto - \frac {1}{z}

. (

Γ
(
1
)

\Gamma (1)

is the modular group

P
S
L
(
2
,
Z
)

PSL(2,Z)

.) The purpose of this article is to present several theoretical results on

Σ
(

m

)

\Sigma (\sqrt m )

, the weight-zero cuspidal spectrum of

Γ
(

m

)

\Gamma (\sqrt m )

, which are of interest from a computational perspective, since they have application to the numerical study both of the spectra themselves and the Fourier coefficients of the associated Maass wave forms. The first of these is the theorem that

Σ
(
1
)
⊂
Σ
(

m

)

\Sigma (1) \subset \Sigma (\sqrt m )

for

m
=
2

m = 2

and

m
=
3

m = 3

. Additional results explicate the action of the Hecke operators, for the three groups in question, upon Maass wave forms, in particular upon their Fourier coefficients. These results are motivated in part by work of Stark—and more recent work of Hejhal and Hejhal and Arno—which demonstrates the importance of the Hecke operators for the numerical study of the Fourier coefficients of Maass wave forms on

Γ
(
1
)

\Gamma (1)

.
Cyclotomy and delta units
Authors: Lazarus Andrew J.
Published: June 2010

In this paper we examine cyclic cubic, quartic, and quintic number fields of prime conductor p containing units that bear a special relationship to the classical Gaussian periods:

η
j

−

η

j
+
1

+
c

{\eta _j} - {\eta _{j + 1}} + c

is a unit for periods

η
j

{\eta _j}

and

c
∈

Z

c \in \mathbb {Z}

.
Numbers having 𝑚 small 𝑚th roots mod 𝑝
Authors: Robinson Raphael M.
Published: June 2010

Here are two typical results about the numbers mentioned in the title: If p is a prime such that

p
≡
1

(
mod

6
)

p \equiv 1 \pmod 6

and

p
>
67

p > 67

, then there are exactly six numbers

mod

p

\bmod \;p

, each of which has six sixth roots less than

2

3
p

2\sqrt {3p}

in absolute value. If p is a prime such that

p
≡
1

(
mod

8
)

p \equiv 1 \pmod 8

, then there is at least one number

mod

p

\bmod \;p

which has eight eighth roots less than

p

3

/

4

{p^{3/4}}

in absolute value.