Complexity of Nonlinear Two-Point Boundary-Value Problems

We study upper and lower bounds on the worst-case ε-complexity of nonlinear two-point boundary-value problems. We deal with general systems of equations with general nonlinear boundary conditions, as well as with second-order scalar problems. Two types of information are considered: standard information defined by the values or partial derivatives of the right-hand-side function, and linear information defined by arbitrary linear functionals. The complexity depends significantly on the problem being solved and on the type of information allowed. We define algorithms based on standard or linear information, using perturbed Newton's iteration, which provide upper bounds on the ε-complexity. The upper and lower bounds obtained differ by a factor of log log 1/ε. Neglecting this factor, for general problems the ε-complexity for the right-hand-side functions having r(r⩾2) continuous bounded partial derivatives turns out to be of order (1/ε)^1/r for standard information, and (1/ε)^1/(r+1) for linear information. For second-order scalar problems, linear information is even more powerful. The ε-complexity in this case is shown to be of order (1/ε)^1/(r+2), while for standard information it remains at the same level as in the general case.     

What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral ∫¹₀ f(x) dg(x) for functions f having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most n evaluations of f and g, and let comp(ε) denote the ε-complexity (the minimal cost of computing an ε-approximation). We show that r(n)≍n^{−min{r, s+1}} and that comp(ε)≍ε^{−1/min{r, s+1}}. We also present an algorithm that computes an ε-approximation at nearly minimal cost.     

The Complexity of Two-Point Boundary-Value Problems with Analytic Data

Previous work on the complexity of elliptic boundary-value problems Lu = f assumed that class F of problem elements f was the unit ball of a Sobolev space. In this paper, we assume that F consists of analytic functions. To be specific, we consider the ϵ-complexity of a model two-point boundary-value problem −u″ + u = f in I = (−1, 1) with natural boundary conditions u′(−1) = u′(1) = 0, and the class F consists of analytic functions f bounded by 1 on a disk of radius ρ ≥ 1 centered at the origin. We find that if ρ > 1, then the ϵ-complexity is Θ(ln(ϵ⁻¹)) as ϵ → 0, and there is a finite element p-method (in the sense of Babuška) whose cost is optimal to within a constant factor. If ρ = 1, we find that the ϵ-complexity is Θ(ln²(ϵ⁻¹)) as ϵ → 0, and there is a finite element (h, p)-method whose cost is optimal to within a constant factor.     

Where Does Smoothness Count the Most for Two-Point Boundary-Value Problems?

We study the complexity of scalar 2mth order elliptic two-point boundary-value problems Lu=f, error being measured in the energy norm. Previous work on the complexity of these problems has generally assumed that we had partial information about the right-hand side f and complete information about the coefficients of L. In this paper, we study the complexity of such problems when, in addition to partial information about f, we have only partial information about the coefficients of L. More precisely, we suppose that f has r derivatives in the L_p-sense, with r⩾−m and p∈[2, ∞], and that L has the usual divergence form Lv=∑_{0⩽i, j⩽m} (−1)ⁱ Dⁱ(a_i, j D^jv), with a_i, j being r_i, j-times continuously differentiable, where r_i, j⩾0. We first suppose that continuous linear information is available. Let r=min{r, min_{0⩽i, j⩽m} {r_i, j−i}}. If r=−m, the problem is unsolvable; for r>−m, we find that the ε-complexity is proportional to (1/ε)^1/(r+m), and we show that a finite element method (FEM) is optimal. We next suppose that only standard information (consisting of function and/or derivative evaluations) is available. Let r_min=min{r, min_{0⩽i, j⩽m} {r_i, j}}. If r_min=0, the problem is unsolvable; for r_min>0, we find that the ε-complexity is proportional to (1/ε)^1/r_min, and we show that a modified FEM (which uses only function evaluations, and not derivatives) is optimal.     

The rate of approximation of Gaussian radial basis neural networks in continuous function space

There have been many studies on the dense theorem of approximation by radial basis feedforword neural networks, and some approximation problems by Gaussian radial basis feedforward neural networks(GRBFNs)in some special function space have also been investigated. This paper considers the approximation by the GRBFNs in continuous function space. It is proved that the rate of approximation by GRNFNs with n~d neurons to any continuous function f defined on a compact subset K(R~d)can be controlled by ω(f, n~(-1/2)), where ω(f, t)is the modulus of continuity of the function f .     

Local complexity functions of interval exchange transformations

We studied numerically complexity functions for interval exchange transformations. We have shown that they grow linearly in time as well as the ?-complexity function. Moreover, we found out that they depend also linearly on ? where ? is the Lebesgue measure of a set of initial points. This allows us to hypothesize that the dimension of the measure related to the ?-complexity function could be determined by studying the dependence of local complexity functions on ?.     

What Is the Complexity of Solution-Restricted Operator Equations?

We study the worst case complexity of operator equations Lu = f where L: G → X is a bounded linear injection of normed linear spaces. Past work on the complexity of such problems has generally required the class F of problem elements f to be the unit ball of X. However, there are many problems for which this choice of F yields unsatisfactory results. Mixed elliptic—hyperbolic problems are one example. the difficulty being that our technical tools are nor strong enough to give good complexity bounds. Ill-posed problems are another example. because we know that the complexity of computing finite-error approximations is infinite if F is a ball in X. In this paper, we pursue another idea. Rather than directly restrict the class F of problem elements f, we will consider problems that are solution-restricted: i.e., we restrict the class U of solution elements u. In particular, we assume that U is the unit hall of a normed linear space W that is densely, continuously embedded in G. The main idea is that our problem can now be reduced to the standard approximation problem of approximating the embedding of W into G.This allows us to characterize optimal information and algorithms for our problem..We use this idea to study three problems: the Tricomi problem (a mixed hyperbolic— elliptic problem arising in the study of transonic flow), the inverse finite Laplace transform (an ill-posed problem arising. e.g.. in geomathematics), and the backwards heat equation. We determine the problem complexity and derive nearly optimal algorithms for each of these problems.     

Reducing network and computation complexities in neural based real-time scheduling scheme

Multiprocessor real-time scheduling is an important issue in many applications. A neural network provides a highly effective method to obtain good solutions for real-time scheduling problems. However, multiprocessor real-time scheduling problems include multiple variables; processor, process and time, and the neural networks have to be presented in three dimensions with these variables. Hence, the corresponding neural networks have more neurons, and synaptic weights, and thus associated network and computational complexities increase. Meanwhile, a neural network using the competitive scheme can provide a highly effective method with less network complexity. Therefore, in this study, a simplified two-dimensional Hopfield-type neural network using competitive rule is introduced for solving three-dimensional multiprocessor real-time scheduling problems. Restated, a two-dimensional network is proposed to lower the neural network dimensions and decrease the number of neurons and hence reduce the network complexity; an M-out-of-N competitive scheme is suggested to greatly reduce the computational complexity. Simulation results reveal that the proposed scheme imposed on the derived energy function with respect to process time and deadline constraints is an appropriate approach to solving these class scheduling problems. Moreover, the computational complexity of the proposed scheme is greatly lowered to O(N × T²).     

Projective Resolutions for Modules over Infinite Groups

We define a notion of complexity for modules over group rings of infinite groups. This generalizes the notion of complexity for modules over group algebras of finite groups. We show that if M is a module over the group ring kG, where k is any ring and G is any group, and M has f-complexity (where f is some complexity function) over some set of finite index subgroups of G, then M has f-complexity over G (up to a direct summand). This generalizes the Alperin-Evens Theorem, which states that if the group G is finite then the complexity of M over G is the maximal complexity of M over an elementary abelian subgroup of G. We also show how we can use this generalization in order to construct projective resolutions for the integral special linear groups, SL(n, ℤ), where n ≥ 2.     

The Complexity of Two-Point Boundary-Value Problems with Piecewise Analytic Data

Previous work on the ε-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the ε-complexity is proportional to ln (ε⁻¹), and there is a finite element p-method (in the sense of Babu ka) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ε < √2. If we know only that there are b ≥ 2 breakpoints, but we de not know their location, then the ε-complexity is proportional to bε⁻¹, and a finite element h-method is nearly optimal. In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L₂ sense.     

Complexity of Linear Problems with a Fixed Output Basis

We use an information-based complexity approach to study the complexity of approximation of linear operators. We assume that the values of a linear operator may be elements of an infinite dimensional space G. It seems reasonable to look for an approximation as a linear combination of some elements g_i from the space G and compute only the coefficients c_i of this linear combination. We study the case when the elements g_i are fixed and compare it with the case where the g_i can be chosen arbitrarily. We show examples of linear problems where a significant output data compression is possible by the use of a nonlinear algorithm, and this nonlinear algorithm is much better than all linear algorithms. We also provide an example of a linear problem for which one piece of information is enough whereas an optimal (minimal cost) algorithm must use information of much higher cardinality.     

Weak Convergence of Cardaliaguet-Euvrard Neural Network Operators Studied Asymptotically

An Nth order asymptotic expansion is established for the error of weak approximation of a special class of functions by the well-known Cardaliaguet-Euvrard neural network operators. This class is made out of functions f that are N times continuously differentiable over R, so that all f,f′,…, f ^(N) have the same compact support and f ^(N) is of bounded variation. This asymptotic expansion involves products of integrals of the network activation bell-shaped function b and f. The rate of the above convergence depends only on the first derivative of involved functions.     

Complexity of differential and integral equations

We are interested in the intrinsic difficulty (or complexity) of computing an approximate solution of the linear operator equation Lu = f. Practical examples of such problems include the cases where L is a known partial differential or integral operator. Problems of the form Lu = f are typically solved under the constraint that only partial information about f is available, such as the values of a finite number of inner products, or the values of f at a finite number of points. It is of interest to determine when algorithms which are in wide use are optimal algorithms, i.e., algorithms which produce an approximation with minimal cost. We are especially interested in determining conditions which are necessary and sufficient for the finite element method (FEM) to be optimal. For the cases of elliptic partial differential equations and of Fredholm integral equations of the second kind, we describe such a condition, in the form of an inequality involving the order of the problem and the degree of the finite element subspace. Suppose this inequality is violated; is the nonoptimality of the FEM inherent in the information used by the FEM, or is it because the FEM uses this information in a nonoptimal manner? The latter is the case; there always exists an algorithm using this information which is optimal. We also discuss the situation in which the information used by the finite element method (which consists of inner products) is not available. Suppose that the only admissible information about f consists of evaluations of f. In the case of the Fredholm problem of the second kind, this information is optimal; moreover, a finite element method in which the inner products are approximated by quadrature rules is an optimal algorithm. However there exist elliptic problems of positive order for which this new information is nonoptimal.     

Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

We study the complexity of Fredholm problems (I−T_k)u=f of the second kind on I^d=[0,1]^d, where T_k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that fW^r,p(I^d) with r>d/p and that kW^s,∞(I^2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Θ(n^−μ+δ), where μ=min{r/d,s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the -complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ^−t, then the -complexity is roughly (1/)^t+1/μ.     

What Is the Complexity of Surface Integration?

We study the worst case complexity of computing ε-approximations of surface integrals. This problem has two sources of partial information: the integrand f and the function g defining the surface. The problem is nonlinear in its dependence on g. Here, f is an r times continuously differentiable scalar function of l variables, and g is an s times continuously differentiable injective function of d variables with l components. We must have d⩽l and s⩾1 for surface integration to be well-defined. Surface integration is related to the classical integration problem for functions of d variables that are min{r, s−1} times continuously differentiable. This might suggest that the complexity of surface integration should be Θ((1/ε)^{d/min{r, s−1}}). Indeed, this holds when d<l and s=1, in which case the surface integration problem has infinite complexity. However, if d⩽l and s⩾2, we prove that the complexity of surface integration is O((1/ε)^d/min{r, s}). Furthermore, this bound is sharp whenever d<l.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

A Two-Dimensional Bisection Envelope Algorithm for Fixed Points

In this paper we present a new algorithm for the two-dimensional fixed point problem f(x)=x on the domain [0, 1]×[0, 1], where f is a Lipschitz continuous function with respect to the infinity norm, with constant 1. The computed approximation x satisfies 6f(x)−x6_∞⩽ε for a specified tolerance ε<0.5. The upper bound on the number of required function evaluations is given by 2⌈log₂(1/ε)⌉+1. Similar bounds were derived for the case of the 2-norm by Z. Huang et al. (1999, J. Complexity15, 200–213), our bound is the first for the infinity norm case.     

Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

This paper deals with the total weighted tardiness minimization with a common due date on a single machine. The best previous approximation algorithm for this problem was recently presented in [H. Kellerer, V.A. Strusevich, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date, Theoretical Computer Science 369 (2006) 230-238] by Kellerer and Strusevich. They proposed a fully polynomial time approximation scheme (FPTAS) of O((n⁶logW)/ε³) time complexity (W is the sum of weights, n is the number of jobs and ε is the error bound). For this problem, we propose a new approach to obtain a more effective FPTAS of O(n²/ε) time complexity. Moreover, a more effective and simpler dynamic programming algorithm is designed.