Partitioned but strongly coupled iteration schemes for nonlinear fluid–structure interaction

We look at the computational procedure of computing the response of a coupled fluid–structure interaction problem. We use the so-called strong fluid–structure coupling––a totally implicit formulation. At each time step in an implicit formulation, new values for the solution variables have to be computed by solving a nonlinear system of equations, where we assume that we have solvers for the subproblems. This is often the case, when we have existing software to solve each subproblem separately, and want to couple both. We show how to solve the overall nonlinear system by using only the solvers for the subproblems. This is achieved not by considering the equilibrium equations, but the fixed-point problem resulting from the solution iteration for each of the subproblems.     

NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems

The boolean hierarchy of k-partitions over NP for k 3 was introduced as a generalization of the well-known boolean hierarchy of sets (2-partitions). The classes of this hierarchy are exactly those classes of NP-partitions which are generated by finite labeled lattices. We generalize the boolean hierarchy of NP-partitions by studying partition classes which are defined by finite labeled posets. We give an exhaustive answer to the question of which relativizable inclusions between partition classes can occur depending on the relation between their defining posets. This provides additional evidence for the validity of the Embedding Conjecture for lattices. The study of the generalized boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the generalized boolean hierarchy of k-partitions over NP is strict, we give a complete characterization when such solution reductions are possible. This resolves in some sense an open question by Hemaspaandra et al.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Implicitization of rational parametric equations

Based on the Gröbner basis method, we present algorithms for a complete solution to the following problems in the implicitization of a set of rational parametric equations. (1) Find a basis of the implicit prime ideal determined by a set of rational parametric equations. (2) Decide whether the parameters of a set of rational parametric equations are independent. (3) If the parameters of a set of rational parametric equations are not independent, reparameterize the parametric equations so that the new parametric equations have independent parameters. (4) Compute the inversion maps of parametric equations, and as a consequence, give a method to decide whether a set of parametric equations is proper. (5) In the case of algebraic curves, find a proper reparameterization for a set of improper parametric equations.     

Binary relations,matrices and inference developments

The relationships among binary relations, directed graphs and boolean matrices are discussed. The development of new relations from given relations is described in terms of boolean matrix operations.The development of new relations from given relations is equivalent to inferring new relationships from the given facts and the operations on these facts. Given a directed graph, one can infer all the facts possible by completing the graph. An alternative method is to store the given facts and upon being queried, one derives the results required.Two algorithms are described which employ matrix operations to make explicit new relationships that are implicit as a result of the given facts and general rules which map sets of relations into new relations. The two algorithms are analyzed in terms of space and time requirements. Comments are made concerning the practicality of the approach.     

四级四阶对角隐式辛Runge-Kutta方法参数计算

1.引 言设有Hamilton系统这坐 H（p1,…,pn,q1,…,qn）是 Hamilton函数,它和t无关.记z=（p1,…;Pn,q1,…,qn）T和Hamilton系统（1）的右端项为f（z）,则（1）可表示为dz/dt=f（z）. 冯康用辛几何的观点提出了计算Hamilton系统的辛差分格式[1].Runge-Kutta方法是求非线性常微分方程（组）数值解的重要单步方法.若能找到具有辛性的Runge-Kutta方法,对于求解非线性 Hamilton系统数值解将具有非常重要的意义.J.M.Sanz-Serna证明     

Locally Implicit Time Integration Strategies in a Discontinuous Galerkin Method for Maxwell’s Equations

An attractive feature of discontinuous Galerkin (DG) spatial discretization is the possibility of using locally refined space grids to handle geometrical details. However, locally refined meshes lead to severe stability constraints on explicit integration methods to numerically solve a time-dependent partial differential equation. If the region of refinement is small relative to the computational domain, the time step size restriction can be overcome by blending an implicit and an explicit scheme where only the solution variables living at fine elements are treated implicitly. The downside of this approach is having to solve a linear system per time step. But due to the assumed small region of refinement relative to the computational domain, the overhead will also be small while the solution can be advanced in time with step sizes determined by the coarse elements. In this paper, we present two locally implicit time integration methods for solving the time-domain Maxwell equations spatially discretized with a DG method. Numerical experiments for two-dimensional problems illustrate the theory and the usefulness of the implicit–explicit approaches in presence of local refinements.     

Universal Boolean Systems

Boolean interaction systems and hard interaction systems define nets of interacting cells. They are based on the same local interaction principle between two cells as interaction nets but do not allow that the structure of nets may evolve. With boolean nets, it is not possible to create or destroy cells or links between existing cells. They are very similar to hardware circuits but based on an implicit rendez-vous information exchange mechanism.If we want to implement such systems using hardware circuits, it is important to define a set of universal combinators that reduces this task to the implementation of a fixed number of known agents. Here, we show how we can simulate every hard interaction system by a universal boolean interaction system composed of three combinators: a duplicator, a NAND gate and a three-state input/output channel.     

Optimally Convergent HDG Method for Third-Order Korteweg–de Vries Type Equations

We develop and analyze a new hybridizable discontinuous Galerkin method for solving third-order Korteweg–de Vries type equations. The approximate solutions are defined by a discrete version of a characterization of the exact solution in terms of the solutions to local problems on each element which are patched together through transmission conditions on element interfaces. We prove that the semi-discrete scheme is stable with proper choices of stabilization function in the numerical traces. For the linearized equation, we carry out error analysis and show that the approximations to the exact solution and its derivatives have optimal convergence rates. In numerical experiments, we use an implicit scheme for time discretization and the Newton–Raphson method for solving systems of nonlinear equations, and observe optimal convergence rates for both the linear and the nonlinear third-order equations.     

Force distribution for the legs of a quadruped walking vehicle

For a walking vehicle with active force control an important problem is how to distribute the forces of the feet. To prevent leg slippage, the active force control of a walking vehicle requires an efficient approach to optimize the foot force distribution. This article presents a new optimization method for a quadruped walking vehicle. We combine the force/moment equilibrium equations with some optimal relations and obtain a set of solvable linear equations. The solution of the equations is the optimal force distribution to prevent leg slippage. To solve the discontinuity problem of optimal solutions, we have used the principle of the convex combination that is an interpolation. Thus the optimal solution found with this algorithm is continuous during a complete locomotion cycle. To solve the force distribution problem for four feet on the ground the maximum computing time is 26 ms on an IBM-compatible DX 80386+803787 only. This optimization method is quite efficient for the controller in real time. © 1997 John Wiley & Sons, Inc.     

Efficient classes of Runge-Kutta methods for two-point boundary value problems

The standard approach to applying IRK methods in the solution of two-point boundary value problems involves the solution of a non-linear system ofn×s equations in order to calculate the stages of the method, wheren is the number of differential equations ands is the number of stages of the implicit Runge-Kutta method. For two-point boundary value problems, we can select a subset of the implicit Runge-Kutta methods that do not require us to solve a non-linear system; the calculation of the stages can be done explicitly, as is the case for explicit Runge-Kutta methods. However, these methods have better stability properties than the explicit Runge-Kutta methods. We have called these new formulas two-point explicit Runge-Kutta (TPERK) methods. Their most important property is that, because their stages can be computed explicity, the solution of a two-point boundary value problem can be computed more efficiently than is possible using an implicit Runge-Kutta method. We have also developed a symmetric subclass of the TPERK methods, called ATPERK methods, which exhibit a number of useful properties.     

A Symbolic-Numerical Method for Finding a Real Solution of an Arbitrary System of Nonlinear Algebraic Equations

In this paper, the author presents a new method for iteratively finding a real solution of an arbitrary system of nonlinear algebraic equations, where the system can be overdetermined or underdetermined and its Jacobian matrix can be of any (positive) rank. When the number of equations is equal to the number of variables and the Jacobian matrix of the system is nonsingular, the method is similar to the well-known Newton's method.The method is a hybrid symbolic-numerical method, in that we utilize some extended procedures from classical computer algebra together with ideas and algorithmic techniques from numerical computation, namely Newton's method and pseudoinverse matrices. First the symbolic techniques are used to transform an arbitrary system of algebraic equations into a set of regular systems. By regular system we mean a system whose Jacobian matrix is of full row rank. Newton-like numerical techniques are then used to find a real solution for each regular system obtained from the symbolic part of the method.The method has a wide range of applicability. It is especially useful for applications in which we need to find some particular solutions from a nonzero-dimensional manifold of real solutions of a system of equations, i.e. the system has infinitely many solutions.We find some mild conditions for the asymptotic convergence of the numerical part of our method. We prove that the asymptotic convergence of the new method is still quadratic while the robustness of the numerical part can be enhanced by techniques like damping as in the regular case. The method has been implemented in Maple andMathematica . Several examples are presented to show that the method works nicely.     

二进神经网络中汉明球突的判定及其逻辑意义

在布尔空间中,汉明球突表达了一类结构清晰的布尔函数, 由于其特殊的几何特性,存在线性可分与线性不可分两种空间结构. 剖析汉明球突的逻辑意义对二进神经网络的规则提取十分重要, 然而,从线性可分的汉明球突中提取具有清晰逻辑意义的规则, 以及如何判定非线性可分的汉明球突,并得到其逻辑意义,仍然是二进神经网络研究中尚未很好解决的问题. 为此,本文首先根据汉明球突在汉明图上的几何特性, 采用真节点加权高度排序的方法, 提出对于任意布尔函数是否为汉明球突的判定算法;然后, 在此基础上利用已知结构的逻辑意义, 将汉明球突分解为若干个已知结构的并集,从而得到汉明球突的逻辑意义; 最后,通过实例说明判定任意布尔函数是否为汉明球突的过程, 并相应得到汉明球突的逻辑表达.     

Numerical Analysis of Strategic Contingent Claims Models

We study the numerical properties of a class of models recently introduced to calculate the values of corporate bonds and other corporate liabilities. Starting from a discrete-time extensive form game representing the consequences of financial distress, these strategic contingent claims models are associated with a particular free-boundary problem. Here we consider the properties of alternative solution techniques applied to this problem. We discuss four solution techniques of the finite difference type: explicit solutions, explicit solutions of the log transformed model, implicit solutions on a regular grid, and dynamically remeshed implicit solutions. To our knowledge this last method has not previously been employed in financial applications. We find that the use of dynamic remeshing can speed calculation solutions enormously. This opens the way to applying strategic contingent claims models in practical applications.     

An extension of the Prelle-Singer method and a Maple implementation

The Prelle-Singer method is a semi-decision algorithm which can be used to solve analytically first order ordinary differential equations which have solutions in terms of elementary functions. In this paper we develop an extension to the Prelle-Singer method which deals with first order ordinary differential equations whose solutions lie outside the scope of the standard Prelle-Singer method. We present a software package in Maple V, Release 5 which implements both the Prelle-Singer method in its original form and our extension. Tests with ordinary differential equations taken from standard references show that our package is able to solve equations where Maple's standard solution routines fail.     

Parallel iterative methods for parabolic equations

For the problems of the parabolic equations in one- and two-dimensional space, the parallel iterative methods are presented to solve the fully implicit difference schemes. The methods presented are based on the idea of domain decomposition in which we divide the linear system of equations into some non-overlapping sub-systems, which are easy to solve in different processors at the same time. The iterative value is proved to be convergent to the difference solution resulted from the implicit difference schemes. Numerical experiments for both one- and two-dimensional problems show that the methods are convergent and may reach the linear speed-up.     

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgroups but is NP-complete otherwise. When S is a monoid or a regular semigroup, we obtain similar dichotomies for the restricted version of the problem where no variable occurs on the right-hand side of each equation. We stress connections between these problems and constraint satisfaction problems. In particular, for any finite domain D and any finite set of relations Γ over D, we construct a finite semigroup S_Γ such that CSP(Γ) is polynomial-time equivalent to the satifiability problem for systems of equations over S_Γ.     

A Hybrid Implicit-Explicit Adaptive Multirate Numerical Scheme for Time-Dependent Equations

We develop a hybrid implicit and explicit adaptive multirate time integration method to solve systems of time-dependent equations that present two significantly different scales. We adopt an iteration scheme to decouple the equations with different time scales. At each iteration, we use an implicit Galerkin method with a fast time-step to solve for the fast scale variables and an explicit method with a slow time-step to solve for the slow variables. We derive an error estimator using a posteriori analysis which controls both the iteration number and the adaptive time-step selection. We present several numerical examples demonstrating the efficiency of our scheme and conclude with a stability analysis for a model problem.     

Numerical solution of linear Fredholm integral equations using sine–cosine wavelets

If we divide the interval [0,1] into N sub-intervals, then sine–cosine wavelets on each sub-interval can approximate any function. This ability helps us to obtain a more accurate approximation of piecewise continuous functions, and, hence, we can obtain more accurate solutions of integral equations. In this article we use a combination of sine–cosine wavelets on the interval [0,1] to solve linear integral equations. We convert the integral equation into a system of linear equations. Numerical examples are given to demonstrate the applicability of the proposed method.