An official website of the United States government
Trefftz methods are high-order Galerkin schemes in which all discrete functions are elementwise solution of the PDE to be approximated. They are viable only when the PDE is linear and its coefficients are piecewise-constant. We introduce a “quasi-Trefftz” discontinuous Galerkin (DG) method for the discretisation of the acoustic wave equation with piecewise-smooth material parameters: the discrete functions are elementwise approximate PDE solutions. We show that the new discretisation enjoys the same excellent approximation properties as the classical Trefftz one, and prove stability and high-order convergence of the DG scheme. We introduce polynomial basis functions for the new discrete spaces and describe a simple algorithm to compute them. The technique we propose is inspired by the generalised plane waves previously developed for time-harmonic problems with variable coefficients; it turns out that in the case of the time-domain wave equation under consideration the quasi-Trefftz approach allows for polynomial basis functions.
more »
« less
Stability and Bifurcations of Equilibria in Networks with Piecewise Linear Interactions
In this paper, we study equilibria of differential equation models for networks. When interactions between nodes are taken to be piecewise constant, an efficient combinatorial analysis can be used to characterize the equilibria. When the piecewise constant functions are replaced with piecewise linear functions, the equilibria are preserved as long as the piecewise linear functions are sufficiently steep. Therefore the combinatorial analysis can be leveraged to understand a broader class of interactions. To better understand how broad this class is, we explicitly characterize how steep the piecewise linear functions must be for the correspondence between equilibria to hold. To do so, we analyze the steady state and Hopf bifurcations which cause a change in the number or stability of equilibria as slopes are decreased. Additionally, we show how to choose a subset of parameters so that the correspondence between equilibria holds for the smallest possible slopes when the remaining parameters are fixed.
more »
« less
- Award ID(s):
- 1839299
- PAR ID:
- 10299854
- Date Published:
- Journal Name:
- International Journal of Bifurcation and Chaos
- Volume:
- 31
- Issue:
- 11
- ISSN:
- 0218-1274
- Page Range / eLocation ID:
- 2130032
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r − 1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component.more » « less
-
null (Ed.)We consider a regression problem, where the correspondence between the input and output data is not available. Such shuffled data are commonly observed in many real world problems. Take flow cytometry as an example: the measuring instruments are unable to preserve the correspondence between the samples and the measurements. Due to the combinatorial nature of the problem, most of the existing methods are only applicable when the sample size is small, and are limited to linear regression models. To overcome such bottlenecks, we propose a new computational framework --- ROBOT --- for the shuffled regression problem, which is applicable to large data and complex models. Specifically, we propose to formulate regression without correspondence as a continuous optimization problem. Then by exploiting the interaction between the regression model and the data correspondence, we propose to develop a hypergradient approach based on differentiable programming techniques. Such a hypergradient approach essentially views the data correspondence as an operator of the regression model, and therefore it allows us to find a better descent direction for the model parameters by differentiating through the data correspondence. ROBOT is quite general, and can be further extended to an inexact correspondence setting, where the input and output data are not necessarily exactly aligned. Thorough numerical experiments show that ROBOT achieves better performance than existing methods in both linear and nonlinear regression tasks, including real-world applications such as flow cytometry and multi-object tracking.more » « less
-
Social insect colonies’ robust and efficient collective behaviors without any central control contribute greatly to their ecological success. Colony migration is a leading subject for studying collective decision-making in migration. In this paper, a general colony migration model with Hill functions in recruitment is proposed to investigate the underlying decision making mechanism and the related dynamical behaviors. Our analysis provides the existence and stability of equilibrium, and the global dynamical behavior of the system. To understand how piecewise functions and Hill functions in recruitment impact colony migration dynamics, the comparisons are performed in both analytic results and bifurcation analysis. Our theoretical results show that the dynamics of the migration system with Hill functions in recruitment differs from that of the migration system with piecewise functions in the following three aspects: (1) all population components in our colony migration model with Hill functions in recruitment are persistent; (2) the colony migration model with Hill functions in recruitment has saddle and saddle-node bifurcations, while the migration system with piecewise functions does not; (3) the system with Hill functions has only equilibrium dynamics, i.e. either has a global stability at one interior equilibrium or has bistablity among two locally stable interior equilibria. Bifurcation analysis shows that the geometrical shape of the Hill functions greatly impacts the dynamics: (1) the system with flatter Hill functions is less likely to exhibit bistability; (2) the system with steeper functions is prone to exhibit bistability, and the steady state of total active workers is closer to that of active workers in the system with piecewise function.more » « less
-
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case approximation ratio or runtime bound. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that a data-driven approach to parameter tuning can lead to significant improvements in performance. This approach uses atraining setof problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide techniques for derivinggeneralization guaranteesthat bound the difference between the algorithm’s average performance over the training set and its expected performance on the unknown distribution. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause a large change in behavior. Prior research [e.g.,12,16,20,62] has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We streamline these analyses with a general theorem that applies whenever an algorithm’s performance is a piecewise-constant, piecewise-linear, or—more generally—piecewise-structuredfunction of its parameters. Our results, which are tight up to logarithmic factors in the worst case, also imply novel bounds for configuring dynamic programming algorithms from computational biology.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S0218127421300329
