Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.     

Rationally 4-periodic biquotients

We give an explicit construction of a maximal torsion-free finite-index subgroup of a certain type of Coxeter group. The subgroup is constructed as the fundamental group of a finite and non-positively curved polygonal complex. First we consider the special case where the universal cover of this polygonal complex is a hyperbolic building, and we construct finite-index embeddings of the fundamental group into certain cocompact lattices of the building. We show that in this special case the fundamental group is an amalgam of surface groups over free groups. We then consider the general case, and construct a finite-index embedding of the fundamental group into the Coxeter group whose Davis complex is the universal cover of the polygonal complex. All of the groups which we embed have minimal index among torsion-free subgroups, and therefore are maximal among torsion-free subgroups.     

The reconstruction of groundwater parameters from head data in an unconfined aquifer

The estimation of groundwater flow parameters from head measurements and other ancillary data is fundamental to the process of modelling a groundwater system. In an unconfined aquifer, the problem is more complex because the governing equation for the well heads, the Boussinesq equation, is non-linear. We consider here a new method that allows for the simultaneous computation of the unconfined groundwater parameters as the unique minimum of a convex functional.     

The Method of Fundamental Solution for a Radially Symmetric Heat Conduction Problem with Variable Coefficient

We consider an inverse heat conduction problem with variable coefficient on an annulus domain. In many practice applications, we cannot know the initial temperature during heat process, therefore we consider a non-characteristic Cauchy problem for the heat equation. The method of fundamental solutions is applied to solve this problem. Due to ill-posedness of this problem, we first discretize the problem and then regularize it in the form of discrete equation. Numerical tests are conducted for showing the effectiveness of the proposed method.     

Three dimensional axisymmetric problems in piezoelectric media: Revisited by a real fundamental solutions based new method

The purpose of the present work is to establish a set of real fundamental solutions for the differential governing equations of three dimensional axisymmetric problems in piezoelectric media. Firstly, conventional complex fundamental solutions are derived by analysis on the eigenvalue problem, and then, Euler’s formula is used to transform them into equivalent real fundamental solutions. As an example of application, the fracture problem of an axisymmetric penny-shaped crack in a piezoelectric layer is resolved by the real fundamental solutions based new method. Theoretical derivation and numerical computation are validated in the special case of a penny-shaped crack in an infinite piezoelectric body. Effects of geometrical parameters and electric-loading coefficient on energy release rates are surveyed and their agreement with the results of existing papers is also indicated. The advantage of such a real fundamental solutions based new method is that it can effectively help to avoid the difficult complex analysis in mixed boundary value problems.     

The impedance boundary-value problem of diffraction by a strip

We consider the impedance boundary-value problem for the Helmholtz equation originated by the problem of wave diffraction by an infinite strip with imperfect conductivity. The two possible different situations of real and complex wave numbers are considered. Bessel potential spaces are used to deal with the problem, and the identification of corresponding operators of single and double layer potentials allow a reformulation of the problem into a system of integral equations. The well-posedness of the problem is obtained for a set of impedance parameters (and wave numbers), after the incorporation of some compatibility conditions on the data. At the end, an improvement of the regularity of the solution is derived for the same set of parameters previously considered.     

On a numerical solution of the Cauchy problem for the Laplace equation by the fundamental solutions method

We discuss a numerical method to solve a Cauchy problem for the Laplace equation in the two-dimensional annular domain. We consider the case that the Cauchy data is given on an arc. We develop an approximation method based of the fundamental solutions method using the least squares method with Tikhonov regularization. The effectiveness of our method is examined by a numerical experiment. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Boundary Integral Solution of the Time-Fractional Diffusion Equation

Here we consider initial boundary value problem for the time–fractional diffusion equation by using the single layer potential representation for the solution. We derive the equivalent boundary integral equation. We will show that the single layer potential admits the usual jump relations and discuss the mapping properties of the single layer operator in the anisotropic Sobolev spaces. Our main theorem is that the single layer operator is coercive in an anisotropic Sobolev space. Based on the coercivity and continuity of the single layer operator we finally show the bijectivity of the operator in a certain range of anisotropic Sobolev spaces.      

Study of a boundary value transmission problem for two-dimensional flows in a piecewise anisotropic inhomogeneous porous layer

We consider a boundary value transmission problem for two-dimensional filtration flows in an anisotropic porous layer consisting of adjacent domains in which the media have essentially different conductivities (permeability and thickness). In general, the layer conductivity is specified by a nonsymmetric second rank tensor whose components are modeled by continuously differentiable functions of coordinates. To study the problem, we use two complex planes, the physical plane and an auxiliary plane, which are related by a homeomorphic (one-to-one and continuous) transformation satisfying an equation of the Beltrami type. On the physical plane, we pose a transmission problem for a rather complicated elliptic system of equations. This problem is reduced on the auxiliary plane to canonical form, which dramatically simplifies the analysis of the problem. Then the problem is reduced to a system of boundary singular integral equations with generalized kernels of the Cauchy type, which are expressed via the fundamental solutions of the main equations. The boundary value transmission problem studied here can be used as a mathematical model of processes arising in the recovery of fluids (water and oil) from natural soil formations of complicated geological structure.     

Submanifolds of the Cayley projective plane with bounded second fundamental form

We consider totally complex submanifolds of the Cayley projective plane with estimates on the length squared of the second fundamental form. We determine those bounds for which the second fundamental form is parallel and for which the submanifold is totally geodesic. The case of totally real submanifolds is also included.     

Cauchy problem for fractional diffusion equations

We consider an evolution equation with the regularized fractional derivative of an order α∈(0,1) with respect to the time variable, and a uniformly elliptic operator with variable coefficients acting in the spatial variables. Such equations describe diffusion on inhomogeneous fractals. A fundamental solution of the Cauchy problem is constructed and investigated.     

Analysis of a finite element PML approximation for the three dimensional time-harmonic Maxwell problem

In our paper [Math. Comp. 76, 2007, 597-614] we considered the acoustic and electromagnetic scattering problems in three spatial dimensions. In particular, we studied a perfectly matched layer (PML) approximation to an electromagnetic scattering problem. We demonstrated both the solvability of the continuous PML approximations and the exponential convergence of the resulting solution to the solution of the original acoustic or electromagnetic problem as the layer increased.

In this paper, we consider finite element approximation of the truncated PML electromagnetic scattering problem. Specifically, we consider approximations which result from the use of Nédélec (edge) finite elements. We show that the resulting finite element problem is stable and gives rise to quasi-optimal convergence when the mesh size is sufficiently small.

     

Time-independence of the solution of the problem of determining the hydraulic conductivity field

We consider the determination of the hydraulic conductivity field of a nonhomogeneous layer with linear seepage of an incompressible fluid in a nonelastic layer. In mathematical terms, the problem is formulated as a Cauchy problem for a partial differential equation of a special form. A theorem is proved which establishes that the solutions obtained for different times are identical.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 57, pp. 67–70, 1985.     

Scattering by Rough Surfaces: the Dirichlet Problem for the Helmholtz Equation in a Non-locally Perturbed Half-plane

We consider the Dirichlet boundary value problem for the Helmholtz equation in a non-locally perturbed half-plane, this problem arising in electromagnetic scattering by one-dimensional rough, perfectly conducting surfaces. We propose a new boundary integral equation formulation for this problem, utilizing the Green's function for an impedance half-plane in place of the standard fundamental solution. We show, at least for surfaces not differing too much from the flat boundary, that the integral equation is uniquely solvable in the space of bounded and continuous functions, and hence that, for a variety of incident fields including an incident plane wave, the boundary value problem for the scattered field has a unique solution satisfying the limiting absorption principle. Finally, a result of continuous dependence of the solution on the boundary shape is obtained.     

Representation of attraction elements in abstract attainability problems with asymptotic constraints

We consider an abstract attainability problem with asymptotic constraints in a topological space. We construct an extension in the class of ultrafilters of widely interpreted measurable spaces. We study an example of a static problem on the asymptotic attainability in the class of layer functions.     

Hold effect in finite torsion of a compressible elastic tube

We consider the application of complex variable method to elastic problem and investigate the nonlinear effect of finite torsion of a compressible elastic composite layer. We obtain that as a result of finite deformation approach, a tube subjected to torsion decreases in radius giving rise to a “hold effect”.     

On a convection–diffusion problem with a weak layer

In this article we consider a model linear convection–diffusion problem with a weak layer. We analyze the singular-perturbation nature of the problem and show that no special precautions are required to cope with the weak layer: a standard upwind scheme on a (quasi-)uniform mesh is sufficient. We give a simple analysis for the method. Thus highlighting that not all problems with a small parameter multiplying the highest-order derivative are suitable for studying boundary-layer phenomena.     

A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem

Surveillance applications require a collection of heterogeneous vehicles to visit a set of targets. We consider a fundamental routing problem that arises in these applications involving two vehicles. Specifically, we consider a routing problem where there are two heterogeneous vehicles that start from distinct initial locations and a set of targets. The objective is to find a tour for each vehicle such that each of the targets is visited at least once by a vehicle and the sum of the distances traveled by the vehicles is minimal. We consider an important special case of this routing problem where the travel costs satisfy the triangle inequality and the following monotonicity property: the first vehicle’s cost of traveling between any two targets is at most equal to the second vehicle’s cost of traveling between the same targets. We present a primal-dual algorithm for this case that provides an approximation ratio of 2.     

New bounds for stabilizing Hele–Shaw flows

We consider the problem of displacement processes in a three-layer fluid in a Hele–Shaw cell modeling enhanced processes of oil recovery by polymer flooding. The middle layer sandwiched between water and oil contains polymer-thickened water. We provide lower bounds on the length of the intermediate layer and on the amount of polymer in the middle layer for stabilizing the leading front to a specified level. We also provide an upper bound on the growth rate of instabilities for a given viscous profile of the middle layer.