Convergence analysis of domain decomposition algorithms with full overlapping for the advection-diffusion problems

The aim of this paper is to study the convergence properties of a time marching algorithm solving advection-diffusion problems on two domains using incompatible discretizations. The basic algorithm is first described, and theoretical and numerical results that illustrate its convergence properties are then presented.

     

Reaching the core of the marriage market through a non-revelation matching mechanism

Each woman indicates a set of acceptable men. Following a line, each man selects his favorite woman among those available to him and to whom he is acceptable. Roth (1982) imposes that women select the whole set of men and Alcalde et al (2000) restrict the choices of women to singleton. We relax these restrictions by allowing women to select any set of men and investigate how this change affects the strategic structure of the games induced by the old procedures.     

Singleton core in many-to-one matching problems

We explore two necessary and sufficient conditions for the singleton core in college admissions problems. One is a condition on the colleges’ preference profiles, called acyclicity, and the other is a condition on their capacity vectors. We also study the implications of our acyclicity condition. The student-optimal stable matching is strongly efficient for the students, given an acyclic profile of the colleges’ preference relations. Even when the colleges’ true preference profile is acyclic, a college may be better off by misreporting its preference when the college-optimal stable mechanism is used.     

Characterization of the core in games with restricted cooperation

Games with restricted cooperation describe situations in which the players are not completely free in forming coalitions. The restrictions in coalition formation can be attributed to economic, hierarchical, political or ethical reasons. In order to manage these situations, the model includes a collection of coalitions which determines the feasible agreements among the agents. The purpose of this paper is to extend the characterization of the core of a cooperative game, made by Peleg [International Journal of Game Theory 15 (1986) 187–200; Handbook of Game Theory with Economic Applications, vol. I. Elsevier Science Publishers B.V., pp. 397–412] to the context of games with restricted cooperation. In order to make the approach as general as possible, we will consider classes of games with restricted cooperation in which the collection of feasible coalitions has a determined structure, and we will impose conditions on that structure to generalize the Peleg’s axiomatization.     

Intrinsic expression of the derivatives in domain optimization problems

It is well-known in domain optimization that the derivative of a cost function with respect to the shape of a domain is a distribution with support lying in the boundary of the domain to be optimized. This existence result is completed with a constructive method giving an explicit expression of this distribution, which can be applied in general cases. The relationship between material and local derivates of any order, provided they are well-defined, is also investigated.     

Characterization of full rank ACI-matrices over fields

An ACI-matrix over a field F$\mathbb{F}$ is a matrix whose entries are polynomials with coefficients on F$\mathbb{F}$, the degree of these polynomials is at most one in a number of indeterminates, and where no indeterminate appears in two different columns. In 2011 Huang and Zhan characterized the m×n$m\times n$ ACI-matrices such that all its completions have rank equal to min{m,n}$\min \{m,n\}$ whenever |F|?max{m,n+1}$|\mathbb{F}|?\max \{m,n+1\}$. We will give a characterization for arbitrary fields by introducing two classes of ACI-matrices: the maximal and the minimal full rank ACI-matrices.     

Lower semicontinuity in domain optimization problems

In the present paper, the lower semicontinuity of certain classes of functionals is studied when the domain of integration, which defines the functionals, is not fixed. For this purpose, a certain class of domains introduced by Chenais is employed. For this class of domains, a basic lemma is proved that plays an essential role in the derivations of the lower-semicontinuity theorems. These theorems are applied to the study of the existence of the optimal domain in domain optimization problems; a boundary-value problem of Neumann type or Dirichlet type is the main constraint in these optimization problems.The author wishes to express his sincere thanks to the reviewer for his valuable comments, which made the paper more readable; the reviewer also pointed out that Lemma 2.1 in the text is a direct corollary to a lemma by Chenais (Ref. 9). He thanks Prof. Y. Sakawa of Osaka University for encouragement.     

Preconditioning of elliptic problems by approximation in the transform domain

Preconditioned conjugate gradient method is applied for solving linear systemsAx=b where the matrixA is the discretization matrix of second-order elliptic operators. In this paper, we consider the construction of the trnasform based preconditioner from the viewpoint of image compression. Given a smooth image, a major portion of the energy is concentrated in the low frequency regions after image transformation. We can view the matrixA as an image and construct the transform based preconditioner by using the low frequency components of the transformed matrix. It is our hope that the smooth coefficients of the given elliptic operator can be approximated well by the low-rank matrix. Numerical results are reported to show the effectiveness of the preconditioning strategy. Some theoretical results about the properties of our proposed preconditioners and the condition number of the preconditioned matrices are discussed.     

A full multigrid method for nonlinear eigenvalue problems

We introduce a type of full multigrid method for the nonlinear eigenvalue problem. The main idea is to transform the solution of the nonlinear eigenvalue problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and nonlinear eigenvalue problems on the coarsest finite element space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient iteration methods for solving boundary value problems can serve as the linear problem solver. We prove that the computational work of this new scheme is truly optimal, the same as solving the linear corresponding boundary value problem. In this case, this type of iteration scheme certainly improves the overfull efficiency of solving nonlinear eigenvalue problems. Some numerical experiments are presented to validate the efficiency of the new method.     

The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems

We study the dynamics of stable marriage and stable roommates markets. Our main tool is the incremental algorithm of Roth and Vande Vate and its generalization by Tan and Hsueh. Beyond proposing alternative proofs for known results, we also generalize some of them to the nonbipartite case. In particular, we show that the lastcomer gets his best stable partner in both incremental algorithms. Consequently, we confirm that it is better to arrive later than earlier to a stable roommates market. We also prove that when the equilibrium is restored after the arrival of a new agent, some agents will be better off under any stable solution for the new market than at any stable solution for the original market. We also propose a procedure to find these agents.     

Axiomatizations of the core on the universal domain and other natural domains

We prove that the core on the set of all transferable utility games with players contained in a universe of at least five members can be axiomatized by the zero inessential game property, covariance under strategic equivalence, anonymity, boundedness, the weak reduced game property, the converse reduced game property, and the reconfirmation property. These properties also characterize the core on certain subsets of games, e.g., on the set of totally balanced games, on the set of balanced games, and on the set of superadditive games. Suitable extensions of these properties yield an axiomatization of the core on sets of nontransferable utility games. Received September 1999/Final version December 2000     

Extremal problems on the Hua domain of the first type

In this paper we study some extremal problems between the Hua domain of the first type and the unit ball.

     

Extremal problems on the Hua domain of the first type

In this paper we study some extremal problems between the Hua domain of the first type and the unit ball.     

Space-time domain decomposition for parabolic problems

We analyze a space-time domain decomposition iteration, for a model advection diffusion equation in one and two dimensions. The discretization of this iteration is the block red-black variant of the waveform relaxation method, and our analysis provides new convergence results for this scheme. The asymptotic convergence rate is super-linear, and it is governed by the diffusion of the error across the overlap between subdomains. Hence, it depends on both the size of this overlap and the diffusion coefficient in the equation. However it is independent of the number of subdomains, provided the size of the overlap remains fixed. The convergence rate for the heat equation in a large time window is initially linear and it deteriorates as the number of subdomains increases. The duration of the transient linear regime is proportional to the length of the time window. For advection dominated problems, the convergence rate is initially linear and it improves as the the ratio of advection to diffusion increases. Moreover, it is independent of the size of the time window and of the number of subdomains. Numerical calculations illustrate our analysis.     

A domain decomposition discretization of parabolic problems

In recent years, domain decomposition methods have attracted much attention due to their successful application to many elliptic and parabolic problems. Domain decomposition methods treat problems based on a domain substructuring, which is attractive for parallel computation, due to the independence among the subdomains. In principle, domain decomposition methods may be applied to the system resulting from a standard discretization of the parabolic problems or, directly, be carried out through a discretization of parabolic problems. In this paper, a direct domain decomposition method is introduced to discretize the parabolic problems. The stability and convergence of this algorithm are analyzed. This work was supported in part by Polish Sciences Foundation under grant 2P03A00524. This work was supported in part by the US Department of Energy under Contracts DE-FG02-92ER25127 and by the Director, Office of Science, Advanced Scientific Computing Research, U.S. Department of Energy under contract DE-AC02-05CH11231.     

Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.