On construction of parallel algorithms in problems of computational mathematics

It is shown by using the example of solution methods for systems of linear algebraic equations that algorithms possessing the important properties of being parallel and asynchronous can be constructed by reducing the problem under consideration to computing a path integral. Earlier, it was shown by the author and his colleagues that, with increasing the dimension n of the system, parallel and asynchronous Monte Carlo algorithms may become better than the corresponding iterative methods. A qualitative explanation of this phenomenon is suggested. The solution of a system of linear algebraic equations of the form X = AX + F admits a simple representation in form of a path integral only under the condition λ₁(A) < 1, where λ₁(A) is an eigenvalue of A with maximum absolute value. Otherwise, a recursive solution procedure with (coarse) parallelism properties can be constructed. However, in this case, additional conditions for synchronizing the algorithm are needed. Finally, it is shown how to obtain efficient analogues of stochastic algorithms (algorithms of the quasi-Monte Carlo method), which exhibit better rate of convergence than those in the Monte Carlo method, on the basis of results obtained by the author and Wagner in [10]. Similar approaches apply to a large class of problems of mathematical and theoretical physics in which integral representations of solutions are known.     

On boundary value problems for systems of nonlinear generalized ordinary differential equations

A general theorem (principle of a priori boundedness) on solvability of the boundary value problem dx = dA(t) · f(t, x), h(x) = 0 is established, where f: [a, b]×R ⁿ → R ⁿ is a vector-function belonging to the Carathéodory class corresponding to the matrix-function A: [a, b] → R ^n×n with bounded total variation components, and h: BV_s([a, b],R ⁿ ) → R ⁿ is a continuous operator. Basing on the mentioned principle of a priori boundedness, effective criteria are obtained for the solvability of the system under the condition x(t₁(x)) = B(x) · x(t ₂(x))+c ₀, where t _i: BV_s([a, b],R ⁿ ) → [a, b] (i = 1, 2) and B: BV_s([a, b], R ⁿ ) → R ⁿ are continuous operators, and c ₀ ∈ R ⁿ .     

On stochastic and quasistochastic methods for solving equations

A modification of the quasi-Monte Carlo method previously suggested by the authors is discussed. This modification is successfully applied to solve integral equations of the second kind thanks to a number of advantages over the quasi-Monte Carlo method. Thus, solving these equations by the quasi-Monte Carlo method requires estimating the sum of a series whose terms are integrals with infinitely increasing constructive dimension. As is known, this is one of the main factors hindering the application of the quasi-Monte Carlo method. Another difficulty is the dominated convergence condition, which ensures the absolute convergence of the series whose sum is to be estimated.The modification under consideration makes it possible to overcome the first difficulty and relax the dominated convergence condition.

Two families of estimates are suggested, which can be applied in the modified algorithm of the quasi-Monte Carlo method. The integral equation

$\phi (x) = \int {k(x,y)\phi (y)\mu (dy) + f(x)(\bmod \mu ),} $

is considered, where x ∈ D ? ? ^s and f and k are given functions defined on the supports of the measures μ and μ ? μ. The values of ? _n (x) = ∫k(x, y)?_{n - 1}(y)μ(dy) + f(x)are estimated step by step. The first group of estimates serves to evaluate ? _n at a fixed point x’:

$\xi _1 (x') = \frac{1}{N}\sum\limits_{j = 1}^N {\xi _1^n (y_j )} ,where\xi _1^n (y) = \frac{{k(x',y)\hat \phi _{n - 1} (y)}}{{p_{n - 1} (y)}} + f(x'),$

here, the y _j are distributed with density p _n?1 and \(\hat \phi _{n - 1} (y)\) is the estimate obtained at the preceding step. The other group of estimates makes it possible to evaluate ? _n at random points.

Optimal parameters of the estimates are found and the corresponding theorems are proved.The theory has been verified on the example of a difference analogue of the Navier-Stokes equation; experimental results are presented.     

Modified Kantorovich theorem and asymptotic approximations of solutions to singularly perturbed systems of ordinary differential equations

The functional equation f(x,ε) = 0 containing a small parameter ε and admitting regular and singular degeneracy as ε → 0 is considered. By the methods of small parameter, a function x _n ⁰(ε) satisfying this equation within a residual error of O(ε ⁿ⁺¹) is found. A modified Newton’s sequence starting from the element x _n ⁰(ε) is constructed. The existence of the limit of Newton’s sequence is based on the NK theorem proven in this work (a new variant of the proof of the Kantorovich theorem substantiating the convergence of Newton’s iterative sequence). The deviation of the limit of Newton’s sequence from the initial approximation x _n ⁰(ε) has the order of O(ε ⁿ⁺¹), which proves the asymptotic character of the approximation x _n ⁰(ε). The method proposed is implemented in constructing an asymptotic approximation of a system of ordinary differential equations on a finite or infinite time interval with a small parameter multiplying the derivatives, but it can be applied to a wider class of functional equations with a small parameters.     

On a functional equation related to derivations in prime rings

In this paper we prove the following result. Let m ≥ 1, n ≥ 1 be fixed integers and let R be a prime ring with m + n + 1 ≤ char(R) or char(R) = 0. Suppose there exists an additive nonzero mapping D : R → R satisfying the relation 2D(x ^n+m+1) = (m + n + 1)(x ^m D(x)x ⁿ + x ⁿ D(x)x ^m ) for all \({x\in R}\). In this case R is commutative and D is a derivation.     

On the constant and step in Jackson’s inequality for best approximations by trigonometric polynomials and by Haar polynomials

We consider the C*-algebra generated by multidimensional integral operators with (?n)th-order homogeneous kernels and by the operators of multiplication by oscillating coefficients of the form |x|^iα. For this algebra, we construct an operator symbolic calculus and obtain necessary and sufficient conditions for the Fredholm property of an operator in terms of this calculus.     

On Causal Invertibility with Respect to a Cone of Integral-Difference Operators in Vector Function Spaces

Let \(\mathbb{S}\) be a cone in ? ⁿ . A bounded linear operator T: L _p (? ⁿ ) → L _p (? ⁿ ) is said to be causal with respect to \(\mathbb{S}\) if the implication x(s) = 0 (s ε W ? \(\mathbb{S}\)) ? (Tx) (s) = 0 (s ε W ? \(\mathbb{S}\)) is valid for any x ε L _p (? ⁿ ) and any open subset W\(\subseteq\) ? ⁿ . The set of all causal operators is a Banach algebra. We describe the spectrum of the operator

$(Tx)(t) = \sum\limits_{n = 1}^\infty {a_n x(t - t_n )} + \int {\mathbb{S}g(s)x(t - s)ds,} \quad t \in \mathbb{R}^n ,$

in this algebra. Here x ranges in a Banach space \(\mathbb{E}\), the a _n are bounded linear operators in \(\mathbb{E}\), and the function g ranges in the set of bounded operators in \(\mathbb{E}\).

     

Series by Haar system with monotone coefficients

Let χ = {χ _n } _n=0 ^∞ be the Haar system normalized in L ²(0, 1) and M = {M _s } _s=1 ^∞ be an arbitrary, increasing sequence of nonnegative integers. For any subsystem of χ of the form {φ _k } = χS = {χ _n } _n∈S , where S = S(M) = {n _k } _k=1 ^∞ = {n ∈ V[p]: p ∈ M}, V[0] = {1, 2} and V[p] = {2 ^p + 1, 2 ^p + 2, …, 2 ^p+1} for p = 1, 2, … a series of the form Σ _i=1 ^∞ a _i φ _i with a _i ↘ 0 is constructed, that is universal with respect to partial series in all classes L ^r (0, 1), r ∈ (0, 1), in the sense of a.e. convergence and in the metric ofL ^r (0, 1). The constructed series is universal in the class of all measurable, finite functions on [0, 1] in the sense of a.e. convergence. It is proved that there exists a series by Haar system with decreasing coefficients, which has the following property: for any ? > 0 there exists a measurable function µ(x), x ∈ [0, 1], such that 0 ≤ µ(x) ≤ 1 and |{x ∈ [0, 1], µ(x) ≠ = 1}| < ?, and the series is universal in the weighted space L _µ[0, 1] with respect to subseries, in the sense of convergence in the norm of L _µ[0, 1].     

Immersed Hypersurfaces in the Unit Sphere S^m＋1 with Constant Blaschke Eigenvalues

For an immersed submanifold x ： M^m→ Sn in the unit sphere S^n without umbilics, an eigenvalue of the Blaschke tensor of x is called a Blaschke eigenvalue of x. It is interesting to determine all hypersurfaces in Sn with constant Blaschke eigenvalues. In this paper, we are able to classify all immersed hypersurfaces in S^m＋1 with vanishing MSbius form and constant Blaschke eigenvalues, in case （1） x has exact two distinct Blaschke eigenvalues, or （2） m = 3. With these classifications, some interesting examples are also presented.     

Special issue: recent progress on iterative methods for large systems of equations

Let A x = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + P Q ^T where \(P, Q \in \mathbb {R}^{n \times k}\) are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system B x = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover, the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence.     

An improvement of the five halves theorem of J. Boardman

Let (M ^m , T) be a smooth involution on a closed smooth m-dimensional manifold and F = ∪ _j=0 ⁿ F ^j (n ≤ m) its fixed point set, where F ^j denotes the union of those components of F having dimension j. The famous Five Halves Theorem of J. Boardman, announced in 1967, establishes that, if F is nonbounding, then m ≤ 5/2n. In this paper we obtain an improvement of the Five Halves Theorem when the top dimensional component of F, F ⁿ , is nonbounding. Specifically, let ω = (i ₁, i ₂, …, i _r ) be a non-dyadic partition of n and s _ω (x ₁, x ₂, …, x _n ) the smallest symmetric polynomial over Z ₂ on degree one variables x ₁, x ₂, …, x _n containing the monomial \(x_1^{i_1 } x_2^{i_2 } \cdots x_r^{i_r }\). Write s _ω (F ⁿ ) ∈ H ⁿ (F ⁿ , Z ₂) for the usual cohomology class corresponding to s _ω (x ₁, x ₂, …, x _n ), and denote by ?(F ⁿ ) the minimum length of a nondyadic partition ω with s _ω (F ⁿ ) ≠ 0 (here, the length of ω = (i ₁, i ₂, …, i _r ) is r). We will prove that, if (M ^m , T) is an involution for which the top dimensional component of the fixed point set, F ⁿ , is nonbounding, then m ≤ 2n + ?(F ⁿ ); roughly speaking, the bound for m depends on the degree of decomposability of the top dimensional component of the fixed point set. Further, we will give examples to show that this bound is best possible.     

On the additive complexity of GCD and LCM matrices

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the n × n matrix formed by the numbers GCD^r(i, k) over the basis {x + y} is asymptotically equal to rn log²n as n→∞, and the complexity of the n × n matrix formed by the numbers LCM^r(i, k) over the basis {x + y,?x} is asymptotically equal to 2rn log₂n as n→∞.     

Interpolation of operators of weak type (ϕ, ϕ)

Considering the measurable and nonnegative functions ? on the half-axis [0, ∞) such that ?(0) = 0 and ?(t) → ∞ as t → ∞, we study the operators of weak type (?, ?) that map the classes of ?-Lebesgue integrable functions to the space of Lebesgue measurable real functions on ?ⁿ. We prove interpolation theorems for the subadditive operators of weak type (?₀, ?₀) bounded in L _∞(?ⁿ) and subadditive operators of weak types (?₀, ?₀) and (?₁, ?₁) in L _?(? ⁿ ) under some assumptions on the nonnegative and increasing functions ?(x) on [0, ∞). We also obtain some interpolation theorems for the linear operators of weak type (?₀, ?₀) bounded from L _∞(?ⁿ) to BMO(? ⁿ). For the restrictions of these operators to the set of characteristic functions of Lebesgue measurable sets, we establish some estimates for rearrangements of moduli of their values; deriving a consequence, we obtain a theorem on the boundedness of operators in rearrangement-invariant spaces.     

Stability of basic sequences via nonlinear <Emphasis Type="Italic">ε</Emphasis>-isometries

In this paper, Let X, Y be two real Banach spaces and ε ≥ 0. A mapping f: X → Y is said to be a standard ε-isometry provided f(0) = 0 and

$$\parallel f\left( x \right) - f\left( y \right)\parallel - \parallel x - y\parallel | \leqslant \varepsilon $$

(1)

for all x, y ∈ X. If ε = 0, then it is simply called a standard isometry. We prove a sufficient and necessary condition for which {f(x_n)}n≥1 is a basic sequence of Y equivalent to {x_n}n≥1 whenever {x_n}n≥1 is a basic sequence in X and f: X → Y is a nonlinear standard isometry. As a corollary we obtain the stability of basic sequences under the perturbation by nonlinear and non-surjective standard ε-isometries.

     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

Linear homotopy method for computing generalized tensor eigenpairs

Let m,m′, n be positive integers such that m ≠ m′. Let A be an mth order n-dimensional tensor, and let ? be an m′th order n-dimensional tensor. λ ∈ ? is called a ?-eigenvalue of A if A x^m?1 = λ?x^m′?1 and ?xm′= 1 for some x ∈ ?ⁿ\{0}. In this paper, we propose a linear homotopy method for solving this eigenproblem. We prove that the method finds all isolated ?-eigenpairs. Moreover, it is easy to implement. Numerical results are provided to show the efficiency of the proposed method.     

Dynamic study of Schröder’s families of first and second kind

The Schröder iterative families of the first and second kind are of great importance in the theory and practice of iterative processes for solving nonlinear equations f(x) = 0. In both cases, the methods E _r (first kind) and S _r (second kind) converge locally to a zero α of f as O(|x _k ? α| ^r ). Although characteristics of these families have been studied in many papers, their dynamic and chaotic behavior has not been completely investigated. In this paper, we compare convergence properties of both iterative schemes using the two methodologies: (i) comparison by numerical examples and (ii) comparison using dynamic study of methods by basins of attraction that enable their graphic visualization. Apart from the visualization of iterative processes, basins of attraction reveal very useful features on iterations such as consumed CPU time and average number of iterations, both as functions of starting points. We demonstrate by several examples that the Schröder family of the second kind S _r possesses better convergence characteristics than the Schröder family of the first kind E _r .     

Congruent elliptic curves with non-trivial Shafarevich-Tate groups: Distribution part

Given a large positive number x and a positive integer k, we denote by Qk(x) the set of congruent elliptic curves E(n): y2= z3- n2 z with positive square-free integers n x congruent to one modulo eight,having k prime factors and each prime factor congruent to one modulo four. We obtain the asymptotic formula for the number of congruent elliptic curves E(n)∈ Qk(x) with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)2. We also get a lower bound for the number of E(n)∈ Qk(x)with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)4. The key ingredient of the proof of these results is an independence property of residue symbols. This property roughly says that the number of positive square-free integers n x with k prime factors and residue symbols(quadratic and quartic) among its prime factors being given compatible values does not depend on the actual values.     

Norms on L of Periodic Interpolation Splines with Equidistant Nodes

We consider the set S _r,n of periodic (with period 1) splines of degree r with deficiency 1 whose nodes are at n equidistant points x_i=i / n. For n-tuples y = (y₀, ... , y_n-1), we take splines s _r,n (y, x) from S _r,n solving the interpolation problem

$$s_{r,n} (y,t_i ) = y_i,$$

where t _i = x _i if r is odd and t _i is the middle of the closed interval [x _i , x _i+1 ] if r is even. For the norms L _r,n ^* of the operator y → s _r,n (y, x) treated as an operator from l¹ to L¹ [0, 1] we establish the estimate

$$L_{r,n}^ * = \frac{4}{{\pi ^2 n}}log min(r,n) + O\left( {\frac{1}{n}} \right)$$

with an absolute constant in the remainder. We study the relationship between the norms L _r,n ^* and the norms of similar operators for nonperiodic splines.

     

On real solutions of systems of equations

Systems of equations f ₁ = ··· = f _n?1 = 0 in ? ⁿ = {x} having the solution x = 0 are considered under the assumption that the quasi-homogeneous truncations of the smooth functions f ₁,..., f _n?1 are independent at x ≠ 0. It is shown that, for n ≠ 2 and n ≠ 4, such a system has a smooth solution which passes through x = 0 and has nonzero Maclaurin series.