Boundary value problems on weighted networks

We present here a systematic study of general boundary value problems on weighted networks that includes the variational formulation of such problems. In particular, we obtain the discrete version of the Dirichlet Principle and we apply it to the analysis of the inverse problem of identifying the conductivities of the network in a very general framework. Our approach is based on the development of an efficient vector calculus on weighted networks which mimetizes the calculus in the smooth case. The key tool is an adequate construction of the tangent space at each vertex. This allows us to consider discrete vector fields, inner products and general metrics. Then, we obtain discrete versions of derivative, gradient, divergence and Laplace-Beltrami operators, satisfying analogous properties to those verified by their continuous counterparts. On the other hand we develop the corresponding integral calculus that includes the discrete versions of the Integration by Parts technique and Green’s Identities. Finally, we apply our discrete vector calculus to analyze the consistency of difference schemes used to solve numerically a Robin boundary value problem in a square.     

An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.This work was supported by U.S. Army Research Office grant DAAG29-82-K-0107.     

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

Petrov-Galerkin methods for natural convection in directional solidification of binary alloys

A Petrov-Galerkin finite element method is presented for calculation of the steady, axisymmetric thermosolutal convection and interface morphology in a model for vertical Bridgman crystal growth of nondilute binary alloys. The Petrov-Galerkin method is based on the formulation for biquadratic elements developed by Heinrich and Zienkiewicz and is introduced into the calculation of the velocity, temperature and concentration fields. The algebraic system is solved simultaneously for the field variables and interface shape by Newton's method. The results of the Petrov-Galerkin method are compared critically with those of Galerkin's method using the same finite element grids. Significant improvements in accuracy are found with the Petrov-Galerkin method only when the mesh is refined and when the formulation of the residual equations is modified to account for the mixed boundary conditions that arise at the solidification interface. Calculations for alloys with stable and unstable solute gradients show the occurrence of classical flow transitions and morphological instabilities in the solidification system.     

Inverse problems of aggregation processes

The coagulation frequency is the key ingredient in the population balance (Smoluchowski) equation of coagulation kinetics. An inverse problem is formulated to extract the coagulation frequency from transient size distributions when these distributions are self-similar. Two numerical examples illustrate the procedure. The first demonstrates the inverse problem for the recovery of singular coagulation frequencies, while the second shows the procedure when self-similarity is approximate. Transient droplet coagulation experiments in a turbulent flow field have been performed. The resulting size distributions are observed to be self-similar. The inverse problem is used to determine the drop coagulation frequency. This frequency shows significant deviation from the coagulation frequencies derived from simple models of drop-drop interactions in a turbulent flow field.     

Increasing efficiency of inverse iteration

Inverse iteration is simple but not very efficient method for computing few eigenvalues with minimal absolute values and corresponding eigenvectors of a symmetric matrix. The idea is to increase its efficiency by technique similar to multigrid methods used for solving linear systems. This approach is not new, but until now multigrid was mostly used for solving linear system which appear in Rayleigh quotient iteration, inverse iteration and related iterative methods. Instead of choosing appropriate coordinates (grids), our algorithm performs inverse iteration on a sequence of subspaces with decreasing dimensions (multispace). Block Lanczos method is used for the selection of a smaller subspace. This will produce a banded matrix, which makes inverse iteration even faster in the smaller dimensions.      

On the decidability of the word problem for amalgamated free products of inverse semigroups

We study inverse semigroup amalgams [S ₁,S ₂;U], where S ₁ and S ₂ are finitely presented inverse semigroups with decidable word problem and U is an inverse semigroup with decidable membership problem in S ₁ and S ₂. We use a modified version of Bennett’s work on the structure of Schützenberger graphs of the ℛ-classes of S ₁* _U S ₂ to state sufficient conditions for the amalgamated free products S ₁* _U S ₂ having decidable word problem.     

Shape reconstruction of an inverse Stokes problem

This paper deals with the shape reconstruction of a viscous incompressible fluid driven by the Stokes flow. For the approximate solution of the ill-posed and nonlinear problem we propose a regularized Newton method. A theoretical foundation for the Newton method is given by establishing the differentiability of the initial boundary value problem with respect to the interior boundary curve in the sense of a domain derivative. The numerical examples show that our theory is useful for practical purpose and the proposed algorithm is feasible.     

A VARIATIONAL EXPECTATION-MAXIMIZATION METHOD FOR THE INVERSE BLACK BODY RADIATION PROBLEM

The inverse black body radiation problem, which is to reconstruct the area temperature distribution from the measurement of power spectrum distribution, is a well-known ill-posed problem. In this paper, a variational expectation-maximization （EM） method is developed and its convergence is studied. Numerical experiments demonstrate that the variational EM method is more efficient and accurate than the traditional methods, including the Tikhonov regularization method, the Landweber method and the conjugate gradient method.