We prove the existence and uniqueness, for wave speeds sufficiently large, of monotone traveling wave solutions connecting stable to unstable spatial equilibria for a class of @math -dimensional lattice differential equations with unidirectional coupling. This class of lattice equations includes some spatial discretizations for hyperbolic conservation laws with a source term as well as a subclass of monotone systems. We obtain a variational characterization of the critical wave speed above which monotone traveling wave solutions are guaranteed to exist. We also discuss non-monotone waves, and the coexistence of monotone and non-monotone waves.
The existence problem in @cite_19 is formulated in terms of increasing traveling waves of negative speed; a change of variables is required to convert to our setting. In terms of , the main hypotheses in @cite_19 are @math ; @math . @math for @math and @math . The first and third conditions above are analogous to our (G1.2) and (G1.3). The second condition above is stronger; it should be thought of as analogous to and allows for the application of monotone iteration techniques. Under these conditions, there is some @math such that a decreasing front exists for all @math (Theorem 1.1 in @cite_19 , reformulated for our setting). In @cite_19 and the companion paper @cite_28 the authors also consider with a piecewise linear @math for which the monotonicity condition above fails, but which is simple enough to admit detailed analysis. In results analogous to ours, the authors describe condititions under which, as @math drops below a critical level, monotone fronts give way to non-monotone fronts that overshoot" and oscillate about their limit at @math .
@cite_28 @cite_19
2031810620 2150477501 2343345052 2000931246
Abstract At the heart of this article will be the study of a branching Brownian motion (BBM) with killing , where individual particles move as Brownian motions with drift − ρ , perform dyadic branching at rate β and are killed on hitting the origin. Firstly, by considering properties of the right-most particle and the extinction probability, we will provide a probabilistic proof of the classical result that the ‘one-sided’ FKPP travelling-wave equation of speed − ρ with solutions f : [ 0 , ∞ ) → [ 0 , 1 ] satisfying f ( 0 ) = 1 and f ( ∞ ) = 0 has a unique solution with a particular asymptotic when ρ 2 β , and no solutions otherwise. Our analysis is in the spirit of the standard BBM studies of [S.C. Harris, Travelling-waves for the FKPP equation via probabilistic arguments, Proc. Roy. Soc. Edinburgh Sect. A 129 (3) (1999) 503–517] and [A.E. Kyprianou, Travelling wave solutions to the K-P-P equation: alternatives to Simon Harris' probabilistic analysis, Ann. Inst. H. Poincare Probab. Statist. 40 (1) (2004) 53–72] and includes an intuitive application of a change of measure inducing a spine decomposition that, as a by product, gives the new result that the asymptotic speed of the right-most particle in the killed BBM is 2 β − ρ on the survival set. Secondly, we introduce and discuss the convergence of an additive martingale for the killed BBM, W λ , that appears of fundamental importance as well as facilitating some new results on the almost-sure exponential growth rate of the number of particles of speed λ ∈ ( 0 , 2 β − ρ ) . Finally, we prove a new result for the asymptotic behaviour of the probability of finding the right-most particle with speed λ > 2 β − ρ . This result combined with Chauvin and Rouault's [B. Chauvin, A. Rouault, KPP equation and supercritical branching Brownian motion in the subcritical speed area. Application to spatial trees, Probab. Theory Related Fields 80 (2) (1988) 299–314] arguments for standard BBM readily yields an analogous Yaglom-type conditional limit theorem for the killed BBM and reveals W λ as the limiting Radon–Nikodým derivative when conditioning the right-most particle to travel at speed λ into the distant future. These lecture notes, based on a course given at the Zurich Clay Summer School (June 23-July 18, 2008), review our current mathematical understanding of the global behaviour of waves on black hole exterior backgrounds. Interest in this problem stems from its relationship to the non-linear stability of the black hole spacetimes themselves as solutions to the Einstein equations, one of the central open problems of general relativity. After an introductory discussion of the Schwarzschild geometry and the black hole concept, the classical theorem of Kay and Wald on the boundedness of scalar waves on the exterior region of Schwarzschild is reviewed. The original proof is presented, followed by a new more robust proof of a stronger boundedness statement. The problem of decay of scalar waves on Schwarzschild is then addressed, and a theorem proving quantitative decay is stated and its proof sketched. This decay statement is carefully contrasted with the type of statements derived heuristically in the physics literature for the asymptotic tails of individual spherical harmonics. Following this, our recent proof of the boundedness of solutions to the wave equation on axisymmetric stationary backgrounds (including slowly-rotating Kerr and Kerr-Newman) is reviewed and a new decay result for slowly-rotating Kerr spacetimes is stated and proved. This last result was announced at the summer school and appears in print here for the first time. A discussion of the analogue of these problems for spacetimes with a positive cosmological constant follows. Finally, a general framework is given for capturing the red-shift effect for non-extremal black holes. This unifies and extends some of the analysis of the previous sections. The notes end with a collection of open problems. This paper concerns the worst-case complexity of Gauss-Seidel method for solving a positive semi-definite linear system; or equivalently, that of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function. The known provable complexity of C-CD can be @math times slower than gradient descent (GD) and @math times slower than randomized coordinate descent (R-CD). However, these gaps seem rather puzzling since so far they have not been observed in practice; in fact, C-CD usually converges much faster than GD and sometimes comparable to R-CD. Thus some researchers believe the gaps are due to the weakness of the proof, but not that of the C-CD algorithm itself. In this paper we show that the gaps indeed exist. We prove that there exists an example for which C-CD takes at least @math or @math operations, where @math is the condition number, @math is a well-studied quantity that determines the convergence rate of R-CD, and @math hides the dependency on @math . This implies that C-CD can indeed be @math times slower than GD, and @math times slower than R-CD in the worst case. Our result establishes one of the few examples in continuous optimization that demonstrates a large gap between a deterministic algorithm and its randomized counterpart. Based on the example, we establish several almost tight complexity bounds of C-CD for quadratic problems. One difficulty with the analysis of the constructed example is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitutes a lower bound for the convergence rate. Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253