The lattice of integer partitions and its infinite extension

In this paper, we use a simple discrete dynamical model to study integer partitions and their lattice. The set of reachable configurations of the model, with the order induced by the transition rule defined on it, is the lattice of all partitions of a positive integer, equipped with a dominance ordering. We first explain how this lattice can be constructed by an algorithm in linear time with respect to its size by showing that it has a self-similar structure. Then, we define a natural extension of the model to infinity, which we compare with the Young lattice. Using a self-similar tree, we obtain an encoding of the obtained lattice which makes it possible to enumerate easily and efficiently all the partitions of a given integer. This approach also gives a recursive formula for the number of partitions of an integer, and some informations on special sets of partitions, such as length bounded partitions.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

Hypergeometric Functions as Infinite-Soliton Tau Functions

It is known that resonant multisoliton solutions depend on higher times and a set of parameters (integrals of motion). We show that soliton tau functions of the Toda lattice (and of the multicomponent Toda lattice) are tau functions of a dual hierarchy, where the higher times and the parameters (integrals of motion) exchange roles. The multisoliton solutions turn out to be rational solutions of the dual hierarchy, and the infinite-soliton tau functions turn out to be hypergeometric-type tau functions of the dual hierarchy. The variables in the dual hierarchies exchange roles. Soliton momenta are related to the Frobenius coordinates of partitions in the decomposition of rational solutions with respect to Schur functions. As an example, we consider partition functions of matrix models: their perturbation series is, on one hand, a hypergeometric tau function and, on the other hand, can be interpreted as an infinite-soliton solution. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 146, No. 2, pp. 222–250, February, 2006.     

Idempotent Block Splitting on Partial Partitions,I: Isotone Operators

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation.     

A shift‐adaptive meshfree method for solving a class of initial‐boundary value problems with moving boundaries in one‐dimensional domain

A new shift‐adaptive meshfree method for solving a class of time‐dependent partial differential equations (PDEs) in a bounded domain (one‐dimensional domain) with moving boundaries and nonhomogeneous boundary conditions is introduced. The radial basis function (RBF) collocation method is combined with the finite difference scheme, because, unlike with Kansa's method, nonlinear PDEs can be converted to a system of linear equations. The grid‐free property of the RBF method is exploited, and a new adaptive algorithm is used to choose the location of the collocation points in the first time step only. In fact, instead of applying the adaptive algorithm on the entire domain of the problem (like with other existing adaptive algorithms), the new adaptive algorithm can be applied only on time steps. Furthermore, because of the radial property of the RBFs, the new adaptive strategy is applied only on the first time step; in the other time steps, the adaptive nodes (obtained in the first time step) are shifted. Thus, only one small system of linear equations must be solved (by LU decomposition method) rather than a large linear or nonlinear system of equations as in Kansa's method (adaptive strategy applied to entire domain), or a large number of small linear systems of equations in the adaptive strategy on each time step. This saves a lot in time and memory usage. Also, Stability analysis is obtained for our scheme, using Von Neumann stability analysis method. Results show that the new method is capable of reducing the number of nodes in the grid without compromising the accuracy of the solution, and the adaptive grading scheme is effective in localizing oscillations due to sharp gradients or discontinuities in the solution. The efficiency and effectiveness of the proposed procedure is examined by adaptively solving two difficult benchmark problems, including a regularized long‐wave equation and a Korteweg‐de Vries problem. © 2016Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1622–1646, 2016     

Ensemble clustering in the belief functions framework

In this paper, belief functions, defined on the lattice of intervals partitions of a set of objects, are investigated as a suitable framework for combining multiple clusterings. We first show how to represent clustering results as masses of evidence allocated to sets of partitions. Then a consensus belief function is obtained using a suitable combination rule. Tools for synthesizing the results are also proposed. The approach is illustrated using synthetic and real data sets.     

Genetic algorithms and cellular automata in aquifer management

A groundwater management problem is presented involving pumping cost minimization with both well discharges and well locations as decision variables. A grid of candidate well locations is set up and optimal arrangements of wells are sought within this discrete space. A genetic algorithm approach is presented with the following particular features: (a) A suitable scaling is applied to the objective function in order to alleviate its regionally flat behavior. (b) No penalty functions are involved in constraint handling. Instead, the feasible region is transformed into a rectangular domain. The transformation introduced is proved to be bijective. (c) A binary representation of well configurations is presented and compared to a combinatorial one. The binary representation necessitates the introduction of specially designed genetic operators. Besides purely genetic algorithms, the concept of cellular automaton is introduced as the basis of an alternative formulation of the optimization problem. The lattice of the cellular automaton provides the discrete set of candidate well positions. The well configuration is represented by a group of agents occupying an equal number of lattice sites. The agents change positions as dictated by the structure of the automaton and, also, by an associated genetic algorithm, which directs the evolution of the whole scheme toward an optimal configuration. An improved performance of this approach is noted and discussed in comparison to the purely genetic algorithm schemes of the present work. A simulated annealing approach is also applied to the same problem for comparison purposes. Finally, a new and more efficient hybrid annealing–genetic approach is introduced and discussed.     

Applications of game theory to threshold logic

Recently,Owen demonstrated an isomorphism between characteristic function games and pseudo-Boolean functions. When a game is interpreted as a function on a lattice, then properties of pseudo-Boolean inequalities can be related to partitions of the lattice. The isomorphism also has important implications for threshold logic. In particular, by using a special reflection map, unate switching functions can be studied via monotone simple games. We can show that every unate switching function can be written as the join threshold functions. Also, using the ideas ofCharnes, Kortanek andKeene, we can give several ways to calculate approximate threshold inequalities for unate switching functions.     

Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization

In bi-parametric linear optimization (LO), perturbation occurs in both the right-hand-side and the objective function data with different parameters. In this paper, the bi-parametric LO problem is considered and we are interested in identifying the regions where the optimal partitions are invariant. These regions are referred to as invariancy regions. It is proved that invariancy regions are separated by vertical and horizontal lines and generate a mesh-like area. It is proved that the boundaries of these regions can be identified in polynomial time. The behavior of the optimal value function on these regions is investigated too.     

The number and stability of limit cycles for planar piecewise linear systems of node–saddle type

The objective of this paper is to study the number and stability of limit cycles for planar piecewise linear (PWL) systems of node–saddle type with two linear regions. Firstly, we give a thorough analysis of limit cycles for Liénard PWL systems of this type, proving one is the maximum number of limit cycles and obtaining necessary and sufficient conditions for the existence and stability of a unique limit cycle. These conditions can be easily verified directly according to the parameters in the systems, and play an important role in giving birth to two limit cycles for general PWL systems. In this step, the tool of a Bendixon-like theorem is successfully employed to derive the existence of a limit cycle. Secondly, making use of the results gained in the first step, we obtain parameter regions where the general PWL systems have at least one, at least two and no limit cycles respectively. In addition for the general PWL systems, some sufficient conditions are presented for the existence and stability of a unique one and exactly two limit cycles respectively. Finally, some numerical examples are given to illustrate the results and especially to show the existence and stability of two nested limit cycles.     

Bosonic Formulas for (k,l)-Admissible Partitions

Bosonic formulas for generating series of partitions with certain restrictions are obtained by solving a set of linear matrix q-difference equations. Some particular cases are related to combinatorial problems arising from solvable lattice models, representation theory and conformal field theory.     

Simplicial Lipschitz optimization without the Lipschitz constant

In this paper we propose a new simplicial partition-based deterministic algorithm for global optimization of Lipschitz-continuous functions without requiring any knowledge of the Lipschitz constant. Our algorithm is motivated by the well-known Direct algorithm which evaluates the objective function on a set of points that tries to cover the most promising subregions of the feasible region. Almost all previous modifications of Direct algorithm use hyper-rectangular partitions. However, other types of partitions may be more suitable for some optimization problems. Simplicial partitions may be preferable when the initial feasible region is either already a simplex or may be covered by one or a manageable number of simplices. Therefore in this paper we propose and investigate simplicial versions of the partition-based algorithm. In the case of simplicial partitions, definition of potentially optimal subregion cannot be the same as in the rectangular version. In this paper we propose and investigate two definitions of potentially optimal simplices: one involves function values at the vertices of the simplex and another uses function value at the centroid of the simplex. We use experimental investigation to compare performance of the algorithms with different definitions of potentially optimal partitions. The experimental investigation shows, that proposed simplicial algorithm gives very competitive results to Direct algorithm using standard test problems and performs particularly well when the search space and the numbers of local and global optimizers may be reduced by taking into account symmetries of the objective function.     

Research on the Fictitious Source Points of the Hybrid Fundamental Solution⁃Based Finite Element Method for Heat Conduction Problems北大核心CSCD

针对热传导问题,提出了杂交基本解有限元法.首先,假设两个独立场:一个为利用基本解线性组合近似的单元域内温度场,另一个为使用与传统有限元法相同形式的辅助网线温度场.然后,利用修正变分泛函将上述两个独立场关联起来,并导出有限元列式.然而,该方法的准确性很大程度上取决于源点的分布和数量,通常将源点布置在单元外部两种虚拟边界上:与单元相似的边界和圆形边界.此外,还提出了双重虚拟边界,并与上述两种源点布局方式进行对比.通过两个典型数值算例,验证了该文方法在不同源点布局下的有效性和对网格畸变的不敏感性.     

Multiscale analysis in Sobolev spaces on bounded domains

We study a multiscale scheme for the approximation of Sobolev functions on bounded domains. Our method employs scattered data sites and compactly supported radial basis functions of varying support radii at scattered data sites. The actual multiscale approximation is constructed by a sequence of residual corrections, where different support radii are employed to accommodate different scales. Convergence theorems for the scheme are proven, and it is shown that the condition numbers of the linear systems at each level are independent of the level, thereby establishing for the first time a mathematical theory for multiscale approximation with scaled versions of a single compactly supported radial basis function at scattered data points on a bounded domain.     

Clifford algebra valued boundary integral equations for three-dimensional elasticity

Applications of Clifford analysis to three-dimensional elasticity are addressed in the present paper. The governing equation for the displacement field is formulated in terms of the Dirac operator and Clifford algebra valued functions so that a general solution is obtained analytically in terms of one monogenic function and one multiple-component spatial harmonic function together with its derivative. In order to solve numerically the three-dimensional problems of elasticity for an arbitrary domain with complicated boundary conditions, Clifford algebra valued boundary integral equations (BIEs) for multiple-component spatial harmonic functions at an observation point, either inside the domain, on the boundary, or outside the domain, are constructed. Both smooth and non-smooth boundaries are considered in the construction. Moreover, the singularities of the integrals are evaluated exactly so that in the end singularity-free BIEs for the observation point on the boundary taking values on Clifford numbers can be obtained. A Clifford algebra valued boundary element method (BEM) based on the singularity-free BIEs is then developed for solving three-dimensional problems of elasticity. The accuracy of the Clifford algebra valued BEM is demonstrated numerically.     

On a Global Optimization Algorithm for Bivariate Smooth Functions

The problem of approximating the global minimum of a function of two variables is considered. A method is proposed rooted in the statistical approach to global optimization. The proposed algorithm partitions the feasible region using a Delaunay triangulation. Only the objective function values are required by the optimization algorithm. The asymptotic convergence rate is analyzed for a class of smooth functions. Numerical examples are provided.     

Uniform partition extensions,a generating functions perspective

In this paper, a bivariate generating function CF(x, y) =f(x)-yf(xy)1-yis investigated, where f(x)= n 0fnxnis a generating function satisfying the functional equation f(x) = 1 + r j=1 m i=j-1aij xif(x)j.In particular, we study lattice paths in which their end points are on the line y = 1. Rooted lattice paths are defined. It is proved that the function CF(x, y) is a generating function defined on some rooted lattice paths with end point on y = 1. So, by a simple and unified method, from the view of lattice paths, we obtain two combinatorial interpretations of this bivariate function and derive two uniform partitions on these rooted lattice paths.     

An explicit spectral collocation method using nonpolynomial basis functions for the time‐dependent Schrödinger equation

We propose a spectral collocation method for the numerical solution of the time‐dependent Schrödinger equation, where the newly developed nonpolynomial functions in a previous study are used as basis functions. Equipped with the new basis functions, various boundary conditions can be imposed exactly. The preferable semi‐implicit time marching schemes are employed for temporal discretization. Moreover, the new basis functions build in a free parameter λ intrinsically, which can be chosen properly so that the semi‐implicit scheme collapses to an explicit scheme. The method is further applied to linear Schrödinger equation set in unbounded domain. The transparent boundary conditions are constructed for time semidiscrete scheme of the linear Schrödinger equation. We employ spectral collocation method using the new basis functions for the spatial discretization, which allows for the exact imposition of the transparent boundary conditions. Comprehensive numerical tests both in bounded and unbounded domain are performed to demonstrate the attractive features of the proposed method.