共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
This paper is on preconditioners for reaction–diffusion problems that are both, uniform with respect to the reaction–diffusion coefficients, and optimal in terms of computational complexity. The considered preconditioners belong to the class of so-called algebraic multilevel iteration (AMLI) methods, which are based on a multilevel block factorization and polynomial stabilization. The main focus of this work is on the construction and on the analysis of a hierarchical splitting of the conforming finite element space of piecewise linear functions that allows to meet the optimality conditions for the related AMLI preconditioner in case of second-order elliptic problems with non-vanishing zero-order term. The finite element method (FEM) then leads to a system of linear equations with a system matrix that is a weighted sum of stiffness and mass matrices. Bounds for the constant \(\gamma \) in the strengthened Cauchy–Bunyakowski–Schwarz inequality are computed for both mass and stiffness matrices in case of a general \(m\) -refinement. Moreover, an additive preconditioner is presented for the pivot blocks that arise in the course of the multilevel block factorization. Its optimality is proven for the case \(m=3\) . Together with the estimates for \(\gamma \) this shows that the construction of a uniformly convergent AMLI method with optimal complexity is possible (for \(m \ge 3\) ). Finally, we discuss the practical application of this preconditioning technique in the context of time-periodic parabolic optimal control problems. 相似文献
3.
Results of Schlipf (J Comput Syst Sci 51:64?C86, 1995) and Fitting (Theor Comput Sci 278:25?C51, 2001) show that the well-founded semantics of a finite predicate logic program can be quite complex. In this paper, we show that there is a close connection between the construction of the perfect kernel of a $\Pi^0_1$ class via the iteration of the Cantor?CBendixson derivative through the ordinals and the construction of the well-founded semantics for finite predicate logic programs via Van Gelder??s alternating fixpoint construction. This connection allows us to transfer known complexity results for the perfect kernel of $\Pi^0_1$ classes to give new complexity results for various questions about the well-founded semantics ${\mathit{wfs}}(P)$ of a finite predicate logic program P. 相似文献
4.
5.
《Computers & Fluids》2002,31(4-7):397-420
A novel B-spline collocation method for the solution of the incompressible Navier–Stokes equations is presented. The discretization employs B-splines of maximum continuity, yielding schemes with high-resolution power. The Navier–Stokes equations are solved by using a fractional step method, where the projection step is considered as a Div–Grad problem, so that no pressure boundary conditions need to be prescribed. Pressure oscillations are prevented by introducing compatible B-spline bases for the velocity and pressure, yielding efficient schemes of arbitrary order of accuracy. The method is applied to two-dimensional benchmark flows, and mass lumping techniques for cost-effective computation of unsteady problems are discussed. 相似文献
6.
Anatolij Dvurečenskij Flavia Ventriglia 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(10):1027-1034
We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second
one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded
functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra.
The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26
SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic
and logical systems of soft computing”, and MURST, project “Analisi Reale”. 相似文献
7.
Sudipto Guha 《The VLDB Journal The International Journal on Very Large Data Bases》2008,17(6):1509-1535
Synopses construction algorithms have been found to be of interest in query optimization, approximate query answering and
mining, and over the last few years several good synopsis construction algorithms have been proposed. These algorithms have
mostly focused on the running time of the synopsis construction vis-a-vis the synopsis quality. However the space complexity
of synopsis construction algorithms has not been investigated as thoroughly. Many of the optimum synopsis construction algorithms
are expensive in space. For some of these algorithms the space required to construct the synopsis is significantly larger
than the space required to store the input. These algorithms rely on the fact that they require a smaller “working space”
and most of the data can be resident on disc. The large space complexity of synopsis construction algorithms is a handicap
in several scenarios. In the case of streaming algorithms, space is a fundamental constraint. In case of offline optimal or
approximate algorithms, a better space complexity often makes these algorithms much more attractive by allowing them to run
in main memory and not use disc, or alternately allows us to scale to significantly larger problems without running out of
space. In this paper, we propose a simple and general technique that reduces space complexity of synopsis construction algorithms.
As a consequence we show that the notion of “working space” proposed in these contexts is redundant. This technique can be
easily applied to many existing algorithms for synopsis construction problems. We demonstrate the performance benefits of
our proposal through experiments on real-life and synthetic data. We believe that our algorithm also generalizes to a broader
range of dynamic programs beyond synopsis construction.
Sudipto Guha’s research supported in part by an Alfred P. Sloan Research Fellowship and by NSF Awards CCF-0430376, CCF-0644119.A
preliminary version of the paper appeared as “Space efficiency in synopsis construction algorithms”, VLDB Conference 2005,
Trondheim, [19]. 相似文献
8.
9.
Formal logical tools are able to provide some amount of reasoning support for information analysis, but are unable to represent
uncertainty. Bayesian network tools represent probabilistic and causal information, but in the worst case scale as poorly
as some formal logical systems and require specialized expertise to use effectively. We describe a framework for systems that
incorporate the advantages of both Bayesian and logical systems. We define a formalism for the conversion of automatically
generated natural deduction proof trees into Bayesian networks. We then demonstrate that the merging of such networks with
domain-specific causal models forms a consistent Bayesian network with correct values for the formulas derived in the proof.
In particular, we show that hard evidential updates in which the premises of a proof are found to be true force the conclusions
of the proof to be true with probability one, regardless of any dependencies and prior probability values assumed for the
causal model. We provide several examples that demonstrate the generality of the natural deduction system by using inference
schemes not supportable directly in Horn clause logic. We compare our approach to other ones, including some that use non-standard
logics. 相似文献
10.
Yujuan Wang Yongduan Song 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2013,17(11):2007-2019
This paper investigates the dynamic behavior of the modified coupled two-component Camassa–Holm dynamic system arisen from shallow water waves moving. By using a skillfully defined characteristic and a set of newly introduced variables, the original system is converted into a Lagrangian semilinear one in which the associated energy is introduced as an additional variable so as to obtain a well-posed initial-value problem, facilitating the study on the behavior of wave breaking. It is established that the solutions of the system continue as global dissipative solutions after wave breaking, which presents an interesting and useful result for better understanding the inevitable phenomenon before and after wave breaking. 相似文献
11.
《Journal of Symbolic Computation》2004,37(5):629-639
In this paper we compare the approach of Briançon and Maisonobe for computing Bernstein–Sato ideals—based on computations in a Poincaré–Birkhoff–Witt algebra—with the readily available method of Oaku and Takayama. We show that it can deal with interesting examples that have proved intractable so far. 相似文献
12.
Ricardo Baeza-Yates Véronique Bruyère Olivier Delgrange Rodrigo Scheihing 《Theoretical computer science》2009
In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m6). Further experimental results suggest that the maximal size could be a polynomial of O(m7), or even an exponential O(20.4m), where m is the length of the pattern. 相似文献
13.
《Mathematics and computers in simulation》1987,29(5):367-372
We consider the equations governing the electrical and thermal behaviour of a semiconductor device in two dimensions. A non-standard Petrov-Galerkin method is used to obtain a discretisation of the equations for stationary problems. The resulting scheme is a generalization to the two-dimensional case and to the full set of equations of the well-known Scharfetter-Gummel scheme, which is the most successful discretisation for one-dimensional problems. The dependent variables used are the carrier densities, the electrostatic potential and the absolute temperature. 相似文献
14.
Enrique Fernández-Cara Arnaud Münch Diego A. Souza 《Journal of scientific computing》2017,70(2):819-858
The aim of this work is to present some strategies to solve numerically controllability problems for the two-dimensional heat equation, the Stokes equations and the Navier–Stokes equations with Dirichlet boundary conditions. The main idea is to adapt the Fursikov–Imanuvilov formulation, see Fursikov and Imanuvilov (Controllability of Evolutions Equations, Lectures Notes Series, vol 34, Seoul National University, 1996); this approach has been followed recently for the one-dimensional heat equation by the first two authors. More precisely, we minimize over the class of admissible null controls a functional that involves weighted integrals of the state and the control, with weights that blow up near the final time. The associated optimality conditions can be viewed as a differential system in the three variables \(x_1\), \(x_2\) and t that is second-order in time and fourth-order in space, completed with appropriate boundary conditions. We present several mixed formulations of the problems and, then, associated mixed finite element Lagrangian approximations that are relatively easy to handle. Finally, we exhibit some numerical experiments. 相似文献
15.
Miriam E. Nes Begnum Kyrre M. Begnum 《Universal Access in the Information Society》2012,11(4):347-357
People who suffer from Parkinson’s Disease face many challenges using computers, and mice are particularly problematic input devices. This article describes usability tests of standard peripherals for use by people with Parkinson’s Disease in order to identify optimal combinations with respect to the needs of this user group. The results are used to determine their effect upon inertia, muscle stiffness, tremor, pain, strain and coordination and show that widely available equipment could significantly improve mouse pointer control for many users. The results reflect the diversity of challenges experienced by computer users with Parkinson’s Disease, and also illustrate how projector-based technology may improve computer interaction without risking strain injuries. 相似文献
16.
Weicun Zhang 《International journal of control》2013,86(5):879-896
This article presents a unified understanding and judgement of the stability and convergence of a general self-tuning control (STC) system, which consists of arbitrary control strategy, arbitrary parameter estimation algorithm and a deterministic/stochastic linear time-invariant (LTI) plant. The necessary conditions required for the global stability and convergence of a general STC system are relaxed, i.e. the convergence of parameter estimates is removed for both deterministic and stochastic STC schemes. To reach this goal, ‘virtual equivalent system (VES)’ concept and methodology is adopted. With the help of VES, the original nonlinear dominant (nonlinear in structure) problem is converted to a linear dominant (linear in structure) problem. The results developed in this article show that STC systems are stable and convergent for the abundance of control strategies and parameter estimation algorithms, which will provide great flexibility in the applications of STC. 相似文献
17.
Peter W. Fick E. Harald van Brummelen Kristoffer G. van der Zee 《Computer Methods in Applied Mechanics and Engineering》2010,199(49-52):3369-3385
The numerical solution of fluid–structure-interaction problems poses a paradox in that most of the computational resources are consumed by the subsystem of least practical interest, viz., the fluid. Goal-oriented adaptive discretization methods provide a paradigm to bypass this paradox. Based on the solution of a dual problem, the contribution of local residuals to the error in a specific goal functional is estimated, and only the regions that yield a dominant contribution are refined. In the present work, we address a fundamental complication in the application of goal-oriented adaptivity to fluid–structure-interaction problems, namely, that the treatment of the interface conditions has nontrivial consequences for the properties of the dual problem. In the context of a linearized model problem, we consider two equivalent discretizations differing only on the formulation of the interface coupling terms. By means of an adjoint consistency analysis, we show that only one of these discretizations is adjoint consistent. Numerical experiments convey that the two discretizations behave very differently for the dual problem, and that the adjoint-consistent discretization yields more reliable error estimates. Based on the adjoint-consistent discretization, we finally present some h- and hp-adaptive results, confirming that tremendous savings in computational cost can be realized through the use of goal-oriented refinement strategies. The numerical experiments illustrate that the goal-oriented approach effectively equilibrates the error contributions of the fluid and structure subsystems, which is imperative for efficiently resolving the coupled fluid–structure-interaction problem, and which cannot be accomplished by uniform or residual-based refinement strategies. 相似文献
18.
José Echeveste Arshia Cont Jean-Louis Giavitto Florent Jacquemard 《Discrete Event Dynamic Systems》2013,23(4):343-383
With the advent and availability of powerful personal computing, the computer music research and industry have been focusing on real-time musical interactions between musicians and computers; delegating human-like actions to computers who interact with a musical environment. One common use-case of this kind is Automatic Accompaniment where the system is comprised of a real-time machine listening system that in reaction to recognition of events in a score from a human performer, launches necessary actions for the accompaniment section. While the real-time detection of score events out of live musicians’ performance has been widely addressed in the literature, score accompaniment (or the reactive part of the process) has been rarely discussed. This paper deals with this missing component in the literature from a formal language perspective. We show how language considerations would enable better authoring of time and interaction during programming/composing and how it addresses critical aspects of a musical performance (such as errors) in real-time. We sketch the real-time features required by automatic musical accompaniment seen as a reactive system. We formalize the timing strategies for musical events taking into account the various temporal scales used in music. Various strategies for the handling of synchronization constraints and the handling of errors are presented. We give a formal semantics to model the possible behaviors of the system in terms of Parametric Timed Automata. 相似文献
19.
《Theoretical computer science》2003,292(1):283-298
In 1912, the Norwegian mathematician Axel Thue was the first to describe an overlap-free binary infinite word. This word was generated by a morphism which is called, since the works of Morse, the Thue–Morse morphism. Here, we present two generalizations of the Thue–Morse morphism in the case of alphabets with more than two letters. The extension of the characteristic properties of the word of Thue to the words generated by these morphisms is considered. One of these generalizations corresponds to the construction of Prouhet and a link with the Arshon words is given. In particular, we prove that if n is an even number then the n-letter Arshon word is generated by morphism. 相似文献
20.
Hongliang Fang Shunlin Liang Gerrit Hoogenboom 《International journal of remote sensing》2013,34(4):1039-1065
Advanced information on crop yield is important for crop management and food policy making. A data assimilation approach was developed to integrate remotely sensed data with a crop growth model for crop yield estimation. The objective was to model the crop yield when the input data for the crop growth model are inadequate, and to make the yield forecast in the middle of the growing season. The Cropping System Model (CSM)–Crop Environment Resource Synthesis (CERES)–Maize and the Markov Chain canopy Reflectance Model (MCRM) were coupled in the data assimilation process. The Moderate Resolution Imaging Spectroradiometer (MODIS) Leaf Area Index (LAI) and vegetation index products were assimilated into the coupled model to estimate corn yield in Indiana, USA. Five different assimilation schemes were tested to study the effect of using different control variables: independent usage of LAI, normalized difference vegetation index (NDVI) and enhanced vegetation index (EVI), and synergic usage of LAI and EVI or NDVI. Parameters of the CSM–CERES–Maize model were initiated with the remotely sensed data to estimate corn yield for each county of Indiana. Our results showed that the estimated corn yield agreed very well with the US Department of Agriculture (USDA) National Agricultural Statistics Service (NASS) data. Among different scenarios, the best results were obtained when both MODIS vegetation index and LAI products were assimilated and the relative deviations from the NASS data were less than 3.5%. Including only LAI in the model performed moderately well with a relative difference of 8.6%. The results from using only EVI or NDVI were unacceptable, as the deviations were as high as 21% and ?13% for the EVI and NDVI schemes, respectively. Our study showed that corn yield at harvest could be successfully predicted using only a partial year of remotely sensed data. 相似文献