bluuebunny/crossref_metadata_2025 huggingface dataset:
The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms
Authors: Bramble James H. , Pasciak Joseph E. , Xu Jinchao
Published: June 2010

We provide a theory for the analysis of multigrid algorithms for symmetric positive definite problems with nonnested spaces and noninherited quadratic forms. By this we mean that the form on the coarser grids need not be related to that on the finest, i.e., we do not stay within the standard variational setting. In this more general setting, we give new estimates corresponding to the

V

\mathcal {V}

cycle,

W

\mathcal {W}

cycle and a

V

\mathcal {V}

cycle algorithm with a variable number of smoothings on each level. In addition, our algorithms involve the use of nonsymmetric smoothers in a novel way. We apply this theory to various numerical approximations of second-order elliptic boundary value problems. In our first example, we consider certain finite difference multigrid algorithms. In the second example, we consider a finite element multigrid algorithm with nested spaces, which however uses a prolongation operator that does not coincide with the natural subspace imbedding. The third example gives a multigrid algorithm derived from a loosely coupled sequence of approximation grids. Such a loosely coupled grid structure results from the most natural standard finite element application on a domain with curved boundary. The fourth example develops and analyzes a multigrid algorithm for a mixed finite element method using the so-called Raviart-Thomas elements.
Large-time behavior of solutions of Lax-Friedrichs finite difference equations for hyperbolic systems of conservation laws
Authors: Chern I-Liang
Published: June 2010

We study the large-time behavior of discrete solutions of the Lax-Friedrichs finite difference equations for hyperbolic systems of conservation laws. The initial data considered here are small and tend to a constant state at

x
=
±
∞

x = \pm \infty

. We show that the solutions tend to the discrete diffusion waves at the rate

O
(

t

−
3

/

4
+
1

/

2
p
+
σ

)

O({t^{ - 3/4 + 1/2p + \sigma }})

in

l
p

{l^p}

,

1
≤
p
≤
∞

1 \leq p \leq \infty

, with

σ
>
0

\sigma > 0

being an arbitrarily small constant. The discrete diffusion waves can be constructed from the self-similar solutions of the heat equation and the Burgers equation through an averaging process.
Iterative methods for cyclically reduced nonselfadjoint linear systems. II
Authors: Elman Howard C. , Golub Gene H.
Published: June 2010

We perform an analytic and experimental study of line iterative methods for solving linear systems arising from finite difference discretizations of non-self-adjoint elliptic partial differential equations on two-dimensional domains. The methods consist of performing one step of cyclic reduction, followed by solution of the resulting reduced system by line relaxation. We augment previous analyses of one-line methods, and we derive a new convergence analysis for two-line methods, showing that both classes of methods are highly effective for solving the convection-diffusion equation. In addition, we compare the experimental performance of several variants of these methods, and we show that the methods can be implemented efficiently on parallel architectures.
New sociable numbers
Authors: Flammenkamp Achim
Published: June 2010

An exhaustive search has yielded new sociable groups; one of order 9, two of order 8, and the others of order 4.
On the zeros of the error term for the mean square of |𝜁(\frac{1}2+𝑖𝑡)|
Authors: Ivić A. , te Riele H. J. J.
Published: June 2010

Let

E
(
T
)

E(T)

denote the error term in the asymptotic formula for
\[

∫
0
T

|

ζ

(

1
2

+
i
t

)

|

2

d
t
.

\int _0^T {{{\left | {\zeta \left ( {\frac {1}{2} + it} \right )} \right |}^2}dt.}

\]
The function

E
(
T
)

E(T)

has mean value

π
\pi

. By

t
n

{t_n}

we denote the nth zero of

E
(
T
)
−
π

E(T) - \pi

. Several results concerning

t
n

{t_n}

are obtained, including

t

n
+
1

−

t
n

≪

t
n

1

/

2

{t_{n + 1}} - {t_n} \ll t_n^{1/2}

. An algorithm is presented to compute the zeros of

E
(
T
)
−
π

E(T) - \pi

below a given bound. For

T
≤
500000

T \leq 500000

, 42010 zeros of

E
(
T
)
−
π

E(T) - \pi

were found. Various tables and figures are given, which present a selection of the computational results.
Degenerate kernel method for Hammerstein equations
Authors: Kaneko Hideaki , Xu Yuesheng
Published: June 2010

The classical method of the degenerate kernel method is applied to numerically solve the Hammerstein equations. Several numerical examples are given to demonstrate the effectiveness of the current method. A brief discussion of a number of methods to decompose the kernel is also included.
Some grid refinement schemes for hyperbolic equations with piecewise constant coefficients
Authors: Lin T. , Sochacki J. , Ewing R. , George J.
Published: June 2010

Discontinuities in the coefficients of hyperbolic equations occur both naturally and artificially and must be treated in numerical schemes. Schemes for handling these discontinuities are derived. An interesting stability result is derived and the schemes are shown to be exact under certain restrictions.
Rosenbrock-type methods adapted to differential-algebraic systems
Authors: Schneider Claus
Published: June 2010

We consider the numerical solution of differential-algebraic systems of index one given in Kronecker canonical form. The methods described here are derived from the Rosenbrock approach. Hence, they do not require the solution of nonlinear systems of equations but one evaluation of the Jacobian and one LU decomposition per step. By construction, the s-stage method coincides with a solver for nonlinear equations of order

s
+
1

s + 1

if the stepsize is set to zero. In this sense, the adaptation to differential-algebraic equations is performed. The special structure of the method leads to simplified order conditions and to an easy implementation. Some particular methods up to order 4 are given. Especially, an embedded 4-stage method of order 4 (3) is derived.
Sums of cubes in polynomial rings
Authors: Vaserstein L. N.
Published: June 2010

For any associative ring A with 1 of prime characteristic

≠
0
,
2
,
3

\ne 0,2,3

, every element of A is the sum of three cubes in A.
Local refinement techniques for elliptic problems on cell-centered grids. I. Error analysis
Authors: Ewing R. E. , Lazarov R. D. , Vassilevski P. S.
Published: June 2010

A finite difference technique on rectangular cell-centered grids with local refinement is proposed in order to derive discretizations of second-order elliptic equations of divergence type approximating the so-called balance equation. Error estimates in a discrete

H
1

{H^1}

-norm are derived of order

h

1

/

2

{h^{1/2}}

for a simple symmetric scheme, and of order

h

3

/

2

{h^{3/2}}

for both a nonsymmetric and a more accurate symmetric one, provided that the solution belongs to

H

1
+
α

{H^{1 + \alpha }}

for

α
>

1
2

\alpha > \frac {1}{2}

and

α
>

3
2

\alpha > \frac {3}{2}

, respectively.
Multigrid analysis of finite element methods with numerical integration
Authors: Goldstein Charles I.
Published: June 2010

We analyze multigrid convergence rates when elliptic boundary value problems are discretized using finite element methods with numerical integration. The resulting discrete problem does not fall into the standard variational framework for analyzing multigrid methods since the bilinear forms on different grid levels are not suitably related to each other. We first discuss extensions of the standard variational multigrid theory and then apply these results to the case of numerical quadrature. In particular, it is shown that the

V

\mathcal {V}

-cycle algorithm has a convergence rate independent of grid size under suitable conditions.
Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant
Authors: Li T. Y. , Wang Xiao Shen
Published: June 2010

By a deficient polynomial system of n polynomial equations in n unknowns we mean a system that has fewer solutions than that predicted by the total degree, or the Bézout number, of the system. If the system is m-homogeneous, the Bézout number can be considerably reduced. In this paper, we introduce a homotopy for numerically determining all isolated solutions of deficient m-homogeneous systems. The initial polynomial system Q is chosen which keeps the subschemes of

H
(
x
,
t
)
=
(
1
−
t
)
a
Q
(
x
)
+
t
P
(
x
)

H(x,t) = (1 - t)aQ(x) + tP(x)

at infinity invariant when t varies in [0, 1).
An analysis of a singularly perturbed two-point boundary value problem using only finite element techniques
Authors: Stynes Martin , O’Riordan Eugene
Published: June 2010

We give a new analysis of Petrov-Galerkin finite element methods for solving linear singularly perturbed two-point boundary value problems without turning points. No use is made of finite difference methodology such as discrete maximum principles, nor of asymptotic expansions. On meshes which are either arbitrary or slightly restricted, we derive energy norm and

L
2

{L^2}

norm error bounds. These bounds are uniform in the perturbation parameter. Our proof uses a variation on the classical Aubin-Nitsche argument, which is novel insofar as the

L
2

{L^2}

bound is obtained independently of the energy norm bound.
Order barriers for continuous explicit Runge-Kutta methods
Authors: Owren Brynjulf , Zennaro Marino
Published: June 2010

In this paper we deal with continuous numerical methods for solving initial value problems for ordinary differential equations, the need for which occurs frequently in applications. Whereas most of the commonly used multi-step methods provide continuous extensions by means of an interpolant which is available without making extra function evaluations, this is not always the case for one-step methods. We consider the class of explicit Runge-Kutta methods and provide theorems used to obtain lower bounds for the number of stages required to construct methods of a given uniform order p. These bounds are similar to the Butcher barriers known for the discrete case, and are derived up to order

p
=
5

p = 5

. As far as we know, the examples we present of 8-stage continuous Runge-Kutta methods of uniform order 5 are the first of their kind.
Primitive 𝑡-nomials (𝑡=3,5) over 𝐺𝐹(2) whose degree is a Mersenne exponent ≤44497
Authors: Kurita Yoshiharu , Matsumoto Makoto
Published: June 2010

All of the primitive trinomials over

G
F
(
2
)

GF(2)

with degree p given by one of the Mersenne exponents 19937, 21701, 23209, and 44497 are presented. Also, one example of a primitive pentanomial over

G
F
(
2
)

GF(2)

is presented for each degree up to 44497 that is a Mersenne exponent. The sieve used is briefly described. A problem is posed which conjectures the number of primitive pentanomials of degree p.
On the existence of an integral normal basis generated by a unit in prime extensions of rational numbers
Authors: Jakubec Stanislav , Kostra Juraj , Nemoga Karol
Published: June 2010

In the present paper a necessary condition for a cyclic extension of the rationals of prime degree l to have an integral normal basis generated by a unit is given. For a fixed l, this condition implies that there exists at most a finite number of such fields. A computational method for verifying the existence of an integral normal basis generated by a unit is given. For

l
=
5

l = 5

, all such fields are found.
Asymptotic boundary conditions for dissipative waves: general theory
Authors: Hagstrom Thomas
Published: June 2010

An outstanding issue in the computational analysis of time-dependent problems is the imposition of appropriate radiation boundary conditions at artificial boundaries. In this work we develop accurate conditions based on the asymptotic analysis of wave propagation over long ranges. Employing the method of steepest descent, we identify dominant wave groups and consider simple approximations to the dispersion relation in order to derive local boundary operators. The existence of a small number of dominant wave groups may be expected for systems with dissipation. Estimates of the error as a function of domain size are derived under general hypotheses, leading to convergence results. Some practical aspects of the numerical construction of the asymptotic boundary operators are also discussed.
A table of totally real quintic number fields
Authors: Diaz y Diaz F.
Published: June 2010

We give a table of the 1077 totally real number fields of degree five having a discriminant less than 2 000 000. There are two nonisomorphic fields of discriminant 1 810 969 and two nonisomorphic fields of discriminant 1 891 377. All the other number fields in the table are characterized by their discriminant. Among these fields, three are cyclic and four have a Galois closure whose Galois group is the dihedral group

D
5

{D_5}

. The Galois closure for all the other fields in the table has a Galois group isomorphic to

S
5

{S_5}

.
A stochastic roundoff error analysis for the fast Fourier transform
Authors: Calvetti Daniela
Published: June 2010

We study the accuracy of the output of the Fast Fourier Transform by estimating the expected value and the variance of the accompanying linear forms in terms of the expected value and variance of the relative roundoff errors for the elementary operations of addition and multiplication. We compare the results with the corresponding ones for the direct algorithm for the Discrete Fourier Transform, and we give indications of the relative performances when different rounding schemes are used. We also present the results of numerical experiments run to test the theoretical bounds and discuss their significance.
On a certain (mod 2) identity and a method of proof by expansion
Authors: Blecksmith Richard , Brillhart John , Gerst Irving
Published: June 2010

We prove the congruence
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="product Underscript StartLayout 1st Row n equals 1 2nd Row n not-identical-to 7 left-parenthesis mod 14 right-parenthesis EndLayout Overscript normal infinity Endscripts left-parenthesis 1 minus x Superscript n Baseline right-parenthesis identical-to sigma-summation Underscript negative normal infinity Overscript normal infinity Endscripts left-parenthesis x Superscript n left-parenthesis 3 n plus 2 right-parenthesis Baseline plus x Superscript 7 n left-parenthesis 3 n plus 2 right-parenthesis plus 2 Baseline right-parenthesis left-parenthesis mod 2 right-parenthesis">

∏

n
=
1

n

≢

7

(
mod

14
)

∞

(
1
−

x
n

)
≡

∑

−
∞

∞

(

x

n
(
3
n
+
2
)

+

x

7
n
(
3
n
+
2
)
+
2

)

(
mod

2
)

\prod \limits _{\begin {array}{*{20}{c}} {n = 1} \\ {n \nequiv 7\;\pmod {14}} \\ \end {array} }^\infty {(1 - {x^n}) \equiv \sum \limits _{ - \infty }^\infty {({x^{n(3n + 2)}} + {x^{7n(3n + 2) + 2}})\;\pmod 2} }

\]
by first establishing a related equation, which reduces to the congruence modulo 2. The method of proof (called "expanding zero") is based on a formula of the authors for expanding the product of two triple products. A second proof of the result more fully explicates the various aspects of the method. A parity result for an associated partition function is also included.
The modified Newton method in the solution of stiff ordinary differential equations
Authors: Alexander Roger
Published: June 2010

This paper presents an analysis of the modified Newton method as it is used in codes implementing implicit formulae for integrating stiff ordinary differential equations. We prove that near a smooth solution of the differential system, when the Jacobian is essentially negative dominant and slowly varying, the modified Newton iteration is contractive, converging to the locally unique solution—whose existence is hereby demonstrated—of the implicit equations. This analysis eliminates several common restrictive or unrealistic assumptions, and provides insight for the design of robust codes.
Mixed finite element methods for compressible miscible displacement in porous media
Authors: Chou So-Hsiang , Li Qian
Published: June 2010

A differential system describing compressible miscible displacement in a porous medium is given. The concentration equation is treated by a Galerkin method and the pressure equation is treated by a parabolic mixed finite element method. Optimal-order estimates in

L
2

{L^2}

and almost optimal-order estimates in

L
∞

{L^\infty }

are obtained for the errors in the approximate solutions under the condition that

h
p

2
k
+
2

(
log
⁡

h
c

−
1

)

1

/

2

→
0

h_p^{2k + 2}{(\log h_c^{ - 1})^{1/2}} \to 0

. This condition is much weaker than one given earlier by Douglas and Roberts for the same model. Furthermore, we obtain the

L
∞

(

L
2

(
Ω
)
)

{L^\infty }({L^2}(\Omega ))

-estimates for the time-derivatives of the concentration and the pressure, which were not given by the above authors. In addition, we also consider newer mixed spaces in two or three dimensions.
On the implementation of singly implicit Runge-Kutta methods
Authors: Cooper G. J.
Published: June 2010

A modified Newton method is often used to solve the algebraic equations that arise in the application of implicit Runge-Kutta methods. When the Runge-Kutta method has a coefficient matrix A with a single point spectrum (with eigenvalue

λ
\lambda

), the efficiency of the modified Newton method is much improved by using a similarity transformation of A. Each iteration involves vector transformations. In this article an alternative iteration scheme is obtained which does not require vector transformations and which is simpler in other respects also. Both schemes converge in a finite number of iterations when applied to linear systems of differential equations, but the new scheme uses the nilpotency of

A
−
λ
I

A - \lambda I

to achieve this. Numerical results confirm the predicted convergence for nonlinear systems and indicate that the scheme may be a useful alternative to the modified Newton method for low-dimensional systems. The scheme seems to become less effective as the dimension increases. However, it has clear advantages for parallel computation, making it competitive for high-dimensional systems.
The distribution of Lucas and elliptic pseudoprimes
Authors: Gordon Daniel M. , Pomerance Carl
Published: June 2010

Let

L

(
x
)

\mathcal {L}(x)

denote the counting function for Lucas pseudoprimes, and

E

(
x
)

\mathcal {E}(x)

denote the elliptic pseudoprime counting function. We prove that, for large x,

L

(
x
)
≤
x
L

(
x

)

−
1

/

2

\mathcal {L}(x) \leq xL{(x)^{ - 1/2}}

and

E

(
x
)
≤
x
L

(
x

)

−
1

/

3

\mathcal {E}(x) \leq xL{(x)^{ - 1/3}}

, where
\[

L
(
x
)
=
exp
⁡
(
log
⁡
x
log
⁡
log
⁡
log
⁡
x

/

log
⁡
log
⁡
x
)
.

L(x) = \exp (\log x\log \log \log x/\log \log x).

\]
Stability analysis of the nonlinear Galerkin method
Authors: Temam R.
Published: June 2010

Our object in this article is to describe some numerical schemes for the approximation of nonlinear evolution equations, and to study the stability of the schemes. Spatial discretization can be performed by either spectral or pseudospectral methods, finite elements or finite differences; time discretization is done by two-level schemes, partly or fully explicit. The algorithms that we present stem from the study of the evolution equations from the dynamical systems point of view. They are based on a differentiated treatment of the small and large wave lengths, and they are particularly adapted to the integration of such equations on large intervals of time.
Infinitely differentiable generalized logarithmic and exponential functions
Authors: Walker Peter
Published: June 2010

We construct infinitely differentiable solutions of the functional equation

f
(
x
+
1
)
=

e

f
(
x
)

f(x + 1) = {e^{f(x)}}

. Numerical values are found and their accuracy is discussed.
On the densest lattice packing of centrally symmetric octahedra
Authors: Chaładus Stefan
Published: June 2010

The main purpose of this paper is the calculation of the critical determinant, and therefore the packing constant, for any centrally symmetric octahedron. The results are obtained partially by a numerical computation that is not rigorous. As an application, we prove that the lattice of integer vectors perpendicular to any integer vector
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold n equals left-bracket n 1 comma n 2 comma n 3 comma n 4 right-bracket left-parenthesis 0 less-than-or-equal-to n 1 less-than-or-equal-to n 2 less-than-or-equal-to n 3 less-than-or-equal-to n 4 comma n 4 greater-than 0 right-parenthesis">

n

=
[

n
1

,

n
2

,

n
3

,

n
4

]

(
0
≤

n
1

≤

n
2

≤

n
3

≤

n
4

,

n
4

>
0
)

{\mathbf {n}} = [{n_1},{n_2},{n_3},{n_4}]\;(0 \leq {n_1} \leq {n_2} \leq {n_3} \leq {n_4},{n_4} > 0)

contains a nonzero vector

m

∈

Z

4

{\mathbf {m}} \in {{\mathbf {Z}}^4}

, the height

(
h
(

m

)
=
max

|

m
i

|

)

(h({\mathbf {m}}) = \max |{m_i}|)

of which satisfies
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartLayout 1st Row left-parenthesis i right-parenthesis 2nd Row left-parenthesis ii right-parenthesis 3rd Row left-parenthesis iii right-parenthesis EndLayout StartLayout 1st Row h left-parenthesis bold m right-parenthesis greater-than left-parenthesis four thirds h left-parenthesis bold n right-parenthesis right-parenthesis Superscript 1 slash 3 Baseline if n 4 less-than-or-equal-to minus 2 n 1 plus n 2 plus n 3 comma 2nd Row h left-parenthesis bold m right-parenthesis greater-than left-parenthesis StartFraction 27 Over 19 EndFraction h left-parenthesis bold n right-parenthesis right-parenthesis Superscript 1 slash 3 Baseline in any case comma 3rd Row h left-parenthesis bold m right-parenthesis less-than-or-equal-to h left-parenthesis bold n right-parenthesis Superscript 1 slash 3 Baseline if n 4 greater-than-or-equal-to n 1 plus n 2 plus n 3 period EndLayout">

(i)

(ii)

(iii)

h
(

m

)
>

(

4
3

h
(

n

)
)

1

/

3

if

n
4

≤
−
2

n
1

+

n
2

+

n
3

,

h
(

m

)
>

(

27

19

h
(

n

)
)

1

/

3

in any case,

h
(

m

)
≤
h

(

n

)

1

/

3

if

n
4

≥

n
1

+

n
2

+

n
3

.

\begin {array}{*{20}{c}} {{\text {(i)}}} \\ {{\text {(ii)}}} \\ {{\text {(iii)}}} \\ \end {array} \quad \begin {array}{*{20}{c}} {h({\mathbf {m}}) > {{(\tfrac {4}{3}h({\mathbf {n}}))}^{1/3}}\quad {\text {if}}\;{n_4} \leq - 2{n_1} + {n_2} + {n_3},} \hfill \\ {h({\mathbf {m}}) > {{(\tfrac {{27}}{{19}}h({\mathbf {n}}))}^{1/3}}\quad {\text {in any case,}}} \hfill \\ {h({\mathbf {m}}) \leq h{{({\mathbf {n}})}^{1/3}}\quad {\text {if}}\;{n_4} \geq {n_1} + {n_2} + {n_3}.} \hfill \\ \end {array}

\]
The closing examples show that the above estimations cannot be improved.
Witt equivalence classes of quartic number fields
Authors: Jakubec Stanislav , Marko František
Published: June 2010

It has recently been established that there are exactly seven Witt equivalence classes of quadratic number fields, and then all quadratic and cubic number fields have been classified with respect to Witt equivalence. In this paper we have classified number fields of degree four. Using this classification, we have proved the Conjecture of Szymiczek about the representability of Witt equivalence classes by quadratic extensions of quadratic fields.
The Γ-function revisited: power series expansions and real-imaginary zero lines
Authors: Bohman Jan , Fröberg Carl-Erik
Published: June 2010

Explicit power series expansions of the gamma function are given close to

−
10
,
−
2
,
−
1
,
0
,
1
,
2
,
3
,
4

- 10, - 2, - 1,0,1,2,3,4

, and 10 together with formulas that can be used in other integer points. Further, curves along which the real or imaginary part of the function vanish are presented.
Circulant preconditioners for Toeplitz matrices with positive continuous generating functions
Authors: Chan Raymond H. , Yeung Man-Chung
Published: June 2010

We consider the solution of n-by-n Toeplitz systems

A
n

x
=
b

{A_n}x = b

by the preconditioned conjugate gradient method. The preconditioner

C
n

{C_n}

is the circulant matrix that minimizes

‖

B
n

−

A
n

‖

F

{\left \| {{B_n} - {A_n}} \right \|_F}

over all circulant matrices

B
n

{B_n}

. We show that if the generating function f is a positive

2
π

2\pi

-periodic continuous function, then the spectrum of the preconditioned system

C
n

−
1

A
n

C_n^{ - 1}{A_n}

will be clustered around one. In particular, if the preconditioned conjugate gradient method is applied to solve the preconditioned system, the convergence rate is superlinear.
A Faber series approach to cardinal interpolation
Authors: Chui C. K. , Stöckler J. , Ward J. D.
Published: June 2010

For a compactly supported function

φ
\varphi

in

R

d

{\mathbb {R}^d}

we study quasiinterpolants based on point evaluations at the integer lattice. We restrict ourselves to the case where the coefficient sequence

λ
f

\lambda f

, for given data f, is computed by applying a univariate polynomial q to the sequence

φ

|

Z

d

\varphi {|_{{\mathbb {Z}^d}}}

, and then convolving with the data

f

|

Z

d

f{|_{{\mathbb {Z}^d}}}

. Such operators appear in the well-known Neumann series formulation of quasi-interpolation. A criterion for the polynomial q is given such that the corresponding operator defines a quasi-interpolant. Since our main application is cardinal interpolation, which is well defined if the symbol of

φ
\varphi

does not vanish, we choose q as the partial sum of a certain Faber series. This series can be computed recursively. By this approach, we avoid the restriction that the range of the symbol of

φ
\varphi

must be contained in a disk of the complex plane excluding the origin, which is necessary for convergence of the Neumann series. Furthermore, for symmetric

φ
\varphi

, we prove that the rate of convergence to the cardinal interpolant is superior to the one obtainable from the Neumann series.
Explicit/implicit conservative Galerkin domain decomposition procedures for parabolic problems
Authors: Dawson Clint N. , Dupont Todd F.
Published: June 2010

Several domain decomposition methods for approximating solutions of parabolic problems are given. These methods rely on implicit Galerkin procedures in the subdomains and explicit flux calculation on the inter-domain boundaries. The procedures are conservative both in the subdomains and across inter-domain boundaries. A priori error bounds and experimental results are presented.
On the distribution of a scaled condition number
Authors: Edelman Alan
Published: June 2010

In this note, we give the exact distribution of a scaled condition number used by Demmel to model the probability that matrix inversion is difficult. Specifically, consider a random matrix A and the scaled condition number
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="kappa Subscript upper D Baseline left-parenthesis upper A right-parenthesis equals double-vertical-bar upper A double-vertical-bar Subscript upper F Baseline bullet double-vertical-bar upper A Superscript negative 1 Baseline double-vertical-bar">

κ
D

(
A
)
=

‖
A
‖

F

∙

‖

A

−
1

‖

{\kappa _D}(A) = {\left \| A \right \|_F} \bullet \left \| {{A^{ - 1}}} \right \|

. Demmel provided bounds for the condition number distribution when A has real or complex normally distributed elements. Here, we give the exact formula.
Explicit Faber polynomials on circular sectors
Authors: Gatermann Karin , Hoffmann Christoph , Opfer Gerhard
Published: June 2010

We present explicit and precise expressions for the Faber polynomials on circular sectors up to degree 20. The precision is obtained by modifying (and simultaneously speeding up) an algorithm of Coleman and Smith so that an essential part of the Faber polynomials can be represented using only rational numbers. The growth of the coefficients of the Faber polynomials is determined. In addition, explicit expressions are given for the area two-norm and line two-norm of these polynomials. A conjecture is stated with respect to the uniform (infinity) norm which would also allow the explicit computation of the corresponding uniform norms of the Faber polynomials. Apart from a table of Faber polynomials, there are several other tables and graphs that illustrate the behavior of the Faber polynomials.
Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition
Authors: Hong Y. P. , Pan C.-T.
Published: June 2010

T. Chan has noted that, even when the singular value decomposition of a matrix A is known, it is still not obvious how to find a rank-revealing QR factorization (RRQR) of A if A has numerical rank deficiency. This paper offers a constructive proof of the existence of the RRQR factorization of any matrix A of size

m
×
n

m \times n

with numerical rank r. The bounds derived in this paper that guarantee the existence of RRQR are all of order

n
r

\sqrt {nr}

, in comparison with Chan’s

O
(

2

n
−
r

)

O({2^{n - r}})

. It has been known for some time that if A is only numerically rank-one deficient, then the column permutation

Π
\Pi

of A that guarantees a small

r

n
n

{r_{nn}}

in the QR factorization of

A
Π

A\Pi

can be obtained by inspecting the size of the elements of the right singular vector of A corresponding to the smallest singular value of A. To some extent, our paper generalizes this well-known result.
A new desingularization for vortex methods
Authors: Hou Thomas Y.
Published: June 2010

A new desingularization is introduced for the vortex method. The idea is to subtract off the most singular part in the discrete approximation to the velocity integral and replace it by the velocity of a vortex patch of constant vorticity, which can be evaluated explicitly. Stability and convergence of the method are obtained in the maximum norm. Preliminary numerical results are presented.
Unconditional convergence of some Crank-Nicolson LOD methods for initial-boundary value problems
Authors: Hundsdorfer Willem
Published: June 2010

In this paper convergence properties are discussed for some locally one-dimensional (LOD) splitting methods applied to linear parabolic initial-boundary value problems. We shall consider unconditional convergence, where both the stepsize in time and the meshwidth in space tend to zero, independently of each other.
Analysis of locally stabilized mixed finite element methods for the Stokes problem
Authors: Kechkar Nasserdine , Silvester David
Published: June 2010

In this paper, a locally stabilized finite element formulation of the Stokes problem is analyzed. A macroelement condition which is sufficient for the stability of (locally stabilized) mixed methods based on a piecewise constant pressure approximation is introduced. By satisfying this condition, the stability of the

Q
1

−

P
0

{Q_1} - {P_0}

quadrilateral, and the

P
1

−

P
0

{P_1} - {P_0}

triangular element, can be established.
The computation of sextic fields with a cubic subfield and no quadratic subfield
Authors: Olivier M.
Published: June 2010

We describe six tables of sixth-degree fields K containing a cubic subfield k and no quadratic subfield: one for totally real sextic fields, one for sextic fields with four real places, two for sextic fields with two real places, and two for totally imaginary sextic fields (depending on whether the cubic subfield is totally real or not). The tables provide for each possible discriminant

d
K

{d_K}

of K a quadratic polynomial which defines K/k , the discriminant of the cubic subfield and the Galois group of a Galois closure

N

/

Q

N/\mathbb {Q}

of

K

/

Q

K/\mathbb {Q}

.
On the distribution of quadratic residues and nonresidues modulo a prime number
Authors: Peralta René
Published: June 2010

Let P be a prime number and

a
1

,
…
,

a
t

{a_1}, \ldots ,{a_t}

be distinct integers modulo P. Let x be chosen at random with uniform distribution in

Z
P

{Z_P}

, and let

y
i

=
x
+

a
i

{y_i} = x + {a_i}

. We prove that the joint distribution of the quadratic characters of the

y
i

{y_i}

’s deviates from the distribution of independent fair coins by no more than

t
(
3
+

P

)

/

P

t(3 + \sqrt P )/P

. That is, the probability of

(

y
1

,
…
,

y
t

)

({y_1}, \ldots ,{y_t})

matching any particular quadratic character sequence of length t is in the range

(

1
2

)

t

±
t
(
3
+

P

)

/

P

{\left ( {\frac {1}{2}} \right )^t} \pm t(3 + \sqrt P )/P

. We establish the implications of this bound on the number of occurrences of arbitrary patterns of quadratic residues and nonresidues modulo P. We then explore the randomness complexity of finding these patterns in polynomial time. We give (exponentially low) upper bounds for the probability of failure achievable in polynomial time using, as a source of randomness, no more than one random number modulo P.
Krylov approximations for matrix square roots in stiff boundary value problems
Authors: Schmitt Bernhard A.
Published: June 2010

Recently, we proposed an algebraic difference scheme, with extended stability properties, for linear boundary value problems involving stiff differential equations of first order. Here, an efficient approximation scheme is presented for matrix square roots, which provides the stabilization of that scheme in case of stiffness. It combines the use of low-rank matrix approximations from projections onto Krylov subspaces with an accelerated sign iteration for the matrix square root. The Krylov approximation, being accurate in eigenspaces with large eigenvalues, preserves the stability of the scheme, and the

O
(

n
3

)

O({n^3})

square root computation need be performed only in lower dimension. Operation counts and numerical results show that the effort for the numerical scheme is essentially proportional to the number of stiff components, but not to the norm of the coefficient matrix. Approximation properties of low-rank Krylov matrices, which may be of independent interest, are analyzed.
Searching for primitive roots in finite fields
Authors: Shoup Victor
Published: June 2010

LetGF(pn){\text {GF}}({p^n})be the finite field withpn{p^n}elements, wherepis prime. We consider the problem of how todeterministicallygenerate in polynomial time a subset ofGF(pn){\text {GF}}({p^n})that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements inGF(pn){\text {GF}}({p^n}). We present three results. First, we present a solution to this problem for the case wherepis small, i.e.,p=nO(1)p = {n^{O(1)}}. Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case wherepis large andn=2n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root forGF(p){\text {GF}}(p), assuming the ERH.
A fast Laplace transform based on Laguerre functions
Authors: Strain John
Published: June 2010

In this paper, we present a fast algorithm which evaluates a discrete Laplace transform with N points at M arbitrarily distributed points in

C
(
N
+
M
)

C(N + M)

work, where C depends only on the precision required. Our algorithm breaks even with the direct calculation at

N
=
M
=
20

N = M = 20

, and achieves a speedup of 1000 with 10000 points. It is based on a geometric divide and conquer strategy, combined with the manipulation of Laguerre expansions via a dilation formula for Laguerre functions.
Variational principles and conservation laws in the derivation of radiation boundary conditions for wave equations
Authors: van Daalen Edwin F. G. , Broeze Jan , van Groesen Embrecht
Published: June 2010

Radiation boundary conditions are derived for partial differential equations which describe wave phenomena. Assuming the evolution of the system to be governed by a Lagrangian variational principle, boundary conditions are obtained with Noether’s theorem from the requirement that they transmit some appropriate density—such as the energy density—as well as possible. The theory is applied to a nonlinear version of the Klein-Gordon equation. For this application numerical test results are presented. In an accompanying paper the theory is applied to a two-dimensional wave equation.
On the power of adaptive information for functions with singularities
Authors: Wasilkowski G. W. , Gao F.
Published: June 2010

We study from a probabilistic viewpoint the problem of locating singularities of functions using function evaluations. We show that, under the assumption of a Wiener-like probability distribution on the class of singular functions, an adaptive algorithm can locate a singular point accurately with only a small probability of failure. As an application, we show that an integration algorithm that adaptively locates a singular point is probabilistically superior to nonadaptive algorithms.
Improved convergence rates for intermediate problems
Authors: Beattie Christopher , Greenlee W. M.
Published: June 2010

Improved convergence rate estimates are derived for a variant of Aronszajn-type intermediate problems that is both computationally feasible and convergent for problems with nontrivial essential spectra. In a previous paper the authors obtained rate of convergence estimates for this method in terms of containment gaps between subspaces. In the present work, techniques for estimating relatively unbounded perturbations are refined in order to apply the Kato-Temple inequalities. This yields convergence rates for the intermediate operator eigenvalues in terms of squares of containment gaps between subspaces. Convergence rate estimates are also obtained for the intermediate problem eigenvectors, and comparisons are made with previously known results for the method of special choice.
Doubly cuspidal cohomology for principal congruence subgroups of 𝐺𝐿(3,𝑍)
Authors: Ash Avner , McConnell Mark
Published: June 2010

The cohomology of arithmetic groups is made up of two pieces, the cuspidal and noncuspidal parts. Within the cuspidal cohomology is a subspace— the f-cuspidal cohomology—spanned by the classes that generate representations of the associated finite Lie group which are cuspidal in the sense of finite Lie group theory. Few concrete examples of f-cuspidal cohomology have been computed geometrically, outside the cases of rational rank 1, or where the symmetric space has a Hermitian structure. This paper presents new computations of the f-cuspidal cohomology of principal congruence subgroups

Γ
(
p
)

\Gamma (p)

of

GL

(
3
,

Z

)

{\text {GL}}(3,\mathbb {Z})

of prime level p. We show that the f-cuspidal cohomology of

Γ
(
p
)

\Gamma (p)

vanishes for all

p
⩽
19

p \leqslant 19

with

p
≠
11

p \ne 11

, but that it is nonzero for

p
=
11

p = 11

. We give a precise description of the f-cuspidal cohomology for

Γ
(
11
)

\Gamma (11)

in terms of the f-cuspidal representations of the finite Lie group

GL

(
3
,

Z

/

11
)

{\text {GL}}(3,\mathbb {Z}/11)

. We obtained the result, ultimately, by proving that a certain large complex matrix M is rank-deficient. Computation with the SVD algorithm gave strong evidence that M was rank-deficient; but to prove it, we mixed ideas from numerical analysis with exact computation in algebraic number fields and finite fields.
The effect of numerical quadrature in the 𝑝-version of the finite element method
Authors: Banerjee Uday , Suri Manil
Published: June 2010

We investigate the use of numerical quadrature in the p-version of the finite element method. We describe a set of minimal conditions that the quadrature rules should satisfy, for various types of elements. Under sufficient assumptions of smoothness, we establish optimality of the asymptotic rate of convergence. Some computational results are presented, which illustrate under what conditions overintegration may be useful.
Linear convergence in the shifted 𝑄𝑅 algorithm
Authors: Batterson Steve , Day David
Published: June 2010

Global and asymptotic convergence properties for the QR algorithm with Francis double shift are established for certain orthogonal similarity classes of

4
×
4

4 \times 4

real matrices. It is shown that in each of the classes every unreduced Hessenberg matrix will decouple and that the rate of decoupling is almost always linear. The effect of the EISPACK exceptional shift strategy is shown to be negligible.
Nu-configurations in tiling the square
Authors: Bremner Andrew , Guy Richard K.
Published: June 2010

In order to tile the unit square with rational triangles, at least four triangles are needed. There are four candidate configurations: one is conjectured not to exist; two others are dealt with elsewhere; the fourth is the "nu-configuration," corresponding to rational points on a quartic surface in affine 3-space. This surface is examined via a pencil of elliptic curves. One rank-3 curve is treated in detail, and rational points are given on 772 curves of the pencil. Within the range of the search there are roughly equal numbers of odd and even rank and those of rank 2 or more seem to be at least 0.45 times as numerous as those of rank 0. Symmetrical solutions correspond to rational points on a curve of rank 1, which exhibits an almost periodic behavior.
Exceptional graphs with smallest eigenvalue -2 and related problems
Authors: Bussemaker F. C. , Neumaier A.
Published: June 2010

This paper summarizes the known results on graphs with smallest eigenvalue around

−
2

- 2

, and completes the theory by proving a number of new results, giving comprehensive tables of the finitely many exceptions, and posing some new problems. Then the theory is applied to characterize a class of distance-regular graphs of large diameter by their intersection array.
Steiner triple systems of order 19 with nontrivial automorphism group
Authors: Colbourn Charles J. , Magliveras Spyros S. , Stinson D. R.
Published: June 2010

There are 172,248 Steiner triple systems of order 19 having a nontrivial automorphism group. Computational methods suitable for generating these designs are developed. The use of tactical configurations in conjunction with orderly algorithms underlies practical techniques for the generation of the designs, and the subexponential time isomorphism technique for triple systems is improved in practice to test isomorphisms of the designs. The automorphism group of each of the triple systems is computed, and a summary presented of the number of systems with each possible type of automorphism.
Pointwise simultaneous convergence of extended Lagrange interpolation with additional knots
Authors: Criscuolo Giuliana , Mastroianni Giuseppe , Vértesi Péter
Published: June 2010

In numerical analysis it is important to construct interpolating polynomials approximating a given function and its derivatives simultaneously. The authors define some new good interpolating matrices with "many" nodes close to the endpoints of the interval and also give error estimates.
Blossoming begets 𝐵-spline bases built better by 𝐵-patches
Authors: Dahmen Wolfgang , Micchelli Charles A. , Seidel Hans-Peter
Published: June 2010

The concept of symmetric recursive algorithm leads to new, s-dimensional spline spaces. We present a general scheme for constructing a collection of multivariate B-splines with

k
−
1

k - 1

continuous derivatives whose linear span contains all polynomials of degree at most k. This scheme is different from the one developed earlier by Dahmen and Micchelli and, independently, by Höllig, which was based on combinatorial principles and the geometric interpretation of the B-spline. The new spline space introduced here seems to offer possibilities for economizing the computation for evaluating linear combinations of B-splines.
On the Diophantine equation 𝑥⁶₁+𝑥⁶₂+𝑥⁶₃=𝑦⁶₁+𝑦⁶₂+𝑦⁶₃
Authors: Delorme Jean-Joël
Published: June 2010

In this paper, we develop an elementary method for producing parametric solutions of the equation

x
1
6

+

x
2
6

+

x
3
6

=

y
1
6

+

y
2
6

+

y
3
6

x_1^6 + x_2^6 + x_3^6 = y_1^6 + y_2^6 + y_3^6

by reducing the resolution of a system including it to that of the equation
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartLayout 1st Row left-parenthesis s 1 squared plus left-parenthesis s 1 plus t 1 right-parenthesis squared right-parenthesis left-parenthesis s 2 squared plus left-parenthesis s 2 plus t 2 right-parenthesis squared right-parenthesis left-parenthesis s 3 squared plus left-parenthesis s 3 plus t 3 right-parenthesis squared right-parenthesis 2nd Row equals left-parenthesis t 1 squared plus left-parenthesis s 1 plus t 1 right-parenthesis squared right-parenthesis left-parenthesis t 2 squared plus left-parenthesis s 2 plus t 2 right-parenthesis squared right-parenthesis left-parenthesis t 3 squared plus left-parenthesis s 3 plus t 3 right-parenthesis squared right-parenthesis period EndLayout">

(

s
1
2

+

(

s
1

+

t
1

)

2

)
(

s
2
2

+

(

s
2

+

t
2

)

2

)
(

s
3
2

+

(

s
3

+

t
3

)

2

)

=
(

t
1
2

+

(

s
1

+

t
1

)

2

)
(

t
2
2

+

(

s
2

+

t
2

)

2

)
(

t
3
2

+

(

s
3

+

t
3

)

2

)
.

\begin {array}{*{20}{c}} {(s_1^2 + {{({s_1} + {t_1})}^2})(s_2^2 + {{({s_2} + {t_2})}^2})(s_3^2 + {{({s_3} + {t_3})}^2})} \\ { = (t_1^2 + {{({s_1} + {t_1})}^2})(t_2^2 + {{({s_2} + {t_2})}^2})(t_3^2 + {{({s_3} + {t_3})}^2}).} \\ \end {array}

\]
We give such solutions of degrees 4, 5, 7, 8, 9, and 11.
Reconstruction algorithms in irregular sampling
Authors: Gröchenig Karlheinz
Published: June 2010

A constructive solution of the irregular sampling problem for band-limited functions is given. We show how a band-limited function can be completely reconstructed from any random sampling set whose density is higher than the Nyquist rate, and give precise estimates for the speed of convergence of this iteration method. Variations of this algorithm allow for irregular sampling with derivatives, reconstruction of band-limited functions from local averages, and irregular sampling of multivariate band-limited functions.
Primitive polynomials over finite fields
Authors: Hansen Tom , Mullen Gary L.
Published: June 2010

In this note we extend the range of previously published tables of primitive polynomials over finite fields. For each

p
n

>

10

50

{p^n} > {10^{50}}

with

p
≤
97

p \leq 97

we provide a primitive polynomial of degree n over

F
p

{F_p}

. Moreover, each polynomial has the minimal number of nonzero coefficients among all primitives of degree n over

F
p

{F_p}

.
2-blocks and 2-modular characters of the Chevalley groups 𝐺₂(𝑞)
Authors: Hiss Gerhard , Shamash Josephine
Published: June 2010

We first determine the distribution of the ordinary irreducible characters of the exceptional Chevalley group

G
2

(
q
)

{G_2}(q)

, q odd, into 2-blocks. This is done by using the method of central characters. Then all but two of the irreducible 2-modular characters are determined. The results are given in the form of decomposition matrices. The methods here involve concepts from modular representation theory and symbolic computations with the computer algebra system MAPLE. As a corollary, the smallest degree of a faithful representation of

G
2

(
q
)

{G_2}(q)

, q odd, over a field of characteristic 2 is obtained.
The approximation of the exact boundary conditions at an artificial boundary for linear elastic equations and its applications
Authors: Han Hou De , Wu Xiao Nan
Published: June 2010

The exterior boundary value problems of linear elastic equations are considered. A sequence of approximations to the exact boundary conditions at an artificial boundary is given. Then the original problem is reduced to a boundary value problem on a bounded domain. Furthermore, a finite element approximation of this problem and optimal error estimates are obtained. Finally, a numerical example shows the effectiveness of this method.
On computing the lattice rule criterion 𝑅
Authors: Joe Stephen , Sloan Ian H.
Published: June 2010

Lattice rules are integration rules for approximating integrals of periodic functions over the s-dimensional unit cube. One criterion for measuring the ’goodness’ of lattice rules is the quantity R. This quantity is defined as a sum which contains about

N

s
−
1

{N^{s - 1}}

terms, where N is the number of quadrature points. Although various bounds involving R are known, a procedure for calculating R itself does not appear to have been given previously. Here we show how an asymptotic series can be used to obtain an accurate approximation to R. Whereas an efficient direct calculation of R requires

O
(
N

n
1

)

O(N{n_1})

operations, where

n
1

{n_1}

is the largest ’invariant’ of the rule, the use of this asymptotic expansion allows the operation count to be reduced to

O
(
N
)

O(N)

. A complete error analysis for the asymptotic expansion is given. The results of some calculations of R are also given.