We present a comprehensive computational study of a class of linear system solvers, called {\it Triangle Algorithm} (TA) and {\it Centering Triangle Algorithm} (CTA), developed by Kalantari \cite{kalantari23}. The algorithms compute an approximate solution or minimum-norm solution to $Ax=b$ or $A^TAx=A^Tb$, where $A$ is an $m \times n$ real matrix of arbitrary rank. The algorithms specialize when $A$ is symmetric positive semi-definite. Based on the description and theoretical properties of TA and CTA from \cite{kalantari23}, we give an implementation of the algorithms that is easy-to-use for practitioners, versatile for a wide range of problems, and robust in that our implementation does not necessitate any constraints on $A$. Next, we make computational comparisons of our implementation with the Matlab implementations of two state-of-the-art algorithms, GMRES and ``lsqminnorm". We consider square and rectangular matrices, for $m$ up to $10000$ and $n$ up to $1000000$, encompassing a variety of applications. These results indicate that our implementation outperforms GMRES and ``lsqminnorm" both in runtime and quality of residuals. Moreover, the relative residuals of CTA decrease considerably faster and more consistently than GMRES, and our implementation provides high precision approximation, faster than GMRES reports lack of convergence. With respect to ``lsqminnorm", our implementation runs faster, producing better solutions. Additionally, we present a theoretical study in the dynamics of iterations of residuals in CTA and complement it with revealing visualizations. Lastly, we extend TA for LP feasibility problems, handling non-negativity constraints. Computational results show that our implementation for this extension is on par with those of TA and CTA, suggesting applicability in linear programming and related problems.
相關內容
The objective of this study is to address the difficulty of simplifying the geometric model in which a differential problem is formulated, also called defeaturing, while simultaneously ensuring that the accuracy of the solution is maintained under control. This enables faster and more efficient simulations, without sacrificing accuracy. More precisely, we consider an isogeometric discretisation of an elliptic model problem defined on a two-dimensional hierarchical B-spline computational domain with a complex boundary. Starting with an oversimplification of the geometry, we build a goal-oriented adaptive strategy that adaptively reintroduces continuous geometrical features in regions where the analysis suggests a large impact on the quantity of interest. This strategy is driven by an a posteriori estimator of the defeaturing error based on first-order shape sensitivity analysis, and it profits from the local refinement properties of hierarchical B-splines. The adaptive algorithm is described together with a procedure to generate (partially) simplified hierarchical B-spline geometrical domains. Numerical experiments are presented to illustrate the proposed strategy and its limitations.
In this paper, a class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent implicit fixed-point equation, then introduces a smoothing function to obtain its approximation solutions. The convergence analysis of the algorithm was given, and the efficiency of the algorithms was verified by numerical experiment
Specifications of complex, large scale, computer software and hardware systems can be radically simplified by using simple maps from input sequences to output values. These "state machine maps" provide an alternative representation of classical Moore type state machines. Composition of state machine maps corresponds to state machine products and can be used to specify essentially any type of interconnection as well as parallel and distributed computation. State machine maps can also specify abstract properties of systems and are significantly more concise and scalable than traditional representations of automata. Examples included here include specifications of producer/consumer software, network distributed consensus, real-time digital circuits, and operating system scheduling. The motivation for this work comes from experience designing and developing operating systems and real-time software where weak methods for understanding and exploring designs is a well known handicap. The methods introduced here are based on ordinary discrete mathematics, primitive recursive functions and deterministic state machines and are intended, initially, to aid the intuition and understanding of the system developers. Staying strictly within the boundaries of classical deterministic state machines anchors the methods to the algebraic structures of automata and semigroups, obviates any need for axiomatic deduction systems, "formal methods", or extensions to the model, and makes the specifications more faithful to engineering practice. While state machine maps are obvious representations of state machines, the techniques introduced here for defining and composing them are novel. To illustrate applications, the paper includes a fairly detailed specification and verification of the well-known "Paxos" distributed consensus algorithm plus a number of simpler examples including a digital PID controller.
SeDuMi and SDPT3 are two solvers for solving Semi-definite Programming (SDP) or Linear Matrix Inequality (LMI) problems. A computational performance comparison of these two are undertaken in this paper regarding the Stability of Continuous-time Linear Systems. The comparison mainly focuses on computational times and memory requirements for different scales of problems. To implement and compare the two solvers on a set of well-posed problems, we employ YALMIP, a widely used toolbox for modeling and optimization in MATLAB. The primary goal of this study is to provide an empirical assessment of the relative computational efficiency of SeDuMi and SDPT3 under varying problem conditions. Our evaluation indicates that SDPT3 performs much better in large-scale, high-precision calculations.
In this paper, we study two graph convexity parameters: iteration time and general position number. The iteration time was defined in 1981 in the geodesic convexity, but its computational complexity was still open. The general position number was defined in the geodesic convexity and proved NP-hard in 2018. We extend these parameters to any graph convexity and prove that the iteration number is NP-hard in the $P_3$ convexity and, with this result, we can prove that the iteration time is also NP-hard in the geodesic convexity even in graphs with diameter two, a very natural question which was unsolved since 1981. These results are also important, since they are the last two missing NP-hardness results regarding the ten most studied graph convexity parameters in the geodesic and $P_3$ convexities. Finally, we also prove that the general position number of the monophonic convexity is NP-hard, W[1]-hard (parameterized by the size of the solution) and $n^{1-\varepsilon}$-inapproximable in polynomial time for any $\varepsilon>0$ unless P=NP, even in graphs with diameter two.
Runtime analysis has produced many results on the efficiency of simple evolutionary algorithms like the (1+1) EA, and its analogue called GSEMO in evolutionary multiobjective optimisation (EMO). Recently, the first runtime analyses of the famous and highly cited EMO algorithm NSGA-II have emerged, demonstrating that practical algorithms with thousands of applications can be rigorously analysed. However, these results only show that NSGA-II has the same performance guarantees as GSEMO and it is unclear how and when NSGA-II can outperform GSEMO. We study this question in noisy optimisation and consider a noise model that adds large amounts of posterior noise to all objectives with some constant probability $p$ per evaluation. We show that GSEMO fails badly on every noisy fitness function as it tends to remove large parts of the population indiscriminately. In contrast, NSGA-II is able to handle the noise efficiently on \textsc{LeadingOnesTrailingZeroes} when $p<1/2$, as the algorithm is able to preserve useful search points even in the presence of noise. We identify a phase transition at $p=1/2$ where the expected time to cover the Pareto front changes from polynomial to exponential. To our knowledge, this is the first proof that NSGA-II can outperform GSEMO and the first runtime analysis of NSGA-II in noisy optimisation.
While reachability analysis is one of the most promising approaches for the formal verification of dynamic systems, a major disadvantage preventing a more widespread application is the requirement to manually tune algorithm parameters such as the time step size. Manual tuning is especially problematic if one aims to verify that the system satisfies complicated specifications described by signal temporal logic formulas since the effect the tightness of the reachable set has on the satisfaction of the specification is often non-trivial to see for humans. We address this problem with a fully-automated verifier for linear systems, which automatically refines all parameters for reachability analysis until it can either prove or disprove that the system satisfies a signal temporal logic formula for all initial states and all uncertain inputs. Our verifier combines reachset temporal logic with dependency preservation to obtain a model checking approach whose over-approximation error converges to zero for adequately tuned parameters. While we in this work focus on linear systems for simplicity, the general concept we present can equivalently be applied for nonlinear and hybrid systems.
Federated learning (FL) has been proposed to protect data privacy and virtually assemble the isolated data silos by cooperatively training models among organizations without breaching privacy and security. However, FL faces heterogeneity from various aspects, including data space, statistical, and system heterogeneity. For example, collaborative organizations without conflict of interest often come from different areas and have heterogeneous data from different feature spaces. Participants may also want to train heterogeneous personalized local models due to non-IID and imbalanced data distribution and various resource-constrained devices. Therefore, heterogeneous FL is proposed to address the problem of heterogeneity in FL. In this survey, we comprehensively investigate the domain of heterogeneous FL in terms of data space, statistical, system, and model heterogeneity. We first give an overview of FL, including its definition and categorization. Then, We propose a precise taxonomy of heterogeneous FL settings for each type of heterogeneity according to the problem setting and learning objective. We also investigate the transfer learning methodologies to tackle the heterogeneity in FL. We further present the applications of heterogeneous FL. Finally, we highlight the challenges and opportunities and envision promising future research directions toward new framework design and trustworthy approaches.
When is heterogeneity in the composition of an autonomous robotic team beneficial and when is it detrimental? We investigate and answer this question in the context of a minimally viable model that examines the role of heterogeneous speeds in perimeter defense problems, where defenders share a total allocated speed budget. We consider two distinct problem settings and develop strategies based on dynamic programming and on local interaction rules. We present a theoretical analysis of both approaches and our results are extensively validated using simulations. Interestingly, our results demonstrate that the viability of heterogeneous teams depends on the amount of information available to the defenders. Moreover, our results suggest a universality property: across a wide range of problem parameters the optimal ratio of the speeds of the defenders remains nearly constant.
Neural networks have shown tremendous growth in recent years to solve numerous problems. Various types of neural networks have been introduced to deal with different types of problems. However, the main goal of any neural network is to transform the non-linearly separable input data into more linearly separable abstract features using a hierarchy of layers. These layers are combinations of linear and nonlinear functions. The most popular and common non-linearity layers are activation functions (AFs), such as Logistic Sigmoid, Tanh, ReLU, ELU, Swish and Mish. In this paper, a comprehensive overview and survey is presented for AFs in neural networks for deep learning. Different classes of AFs such as Logistic Sigmoid and Tanh based, ReLU based, ELU based, and Learning based are covered. Several characteristics of AFs such as output range, monotonicity, and smoothness are also pointed out. A performance comparison is also performed among 18 state-of-the-art AFs with different networks on different types of data. The insights of AFs are presented to benefit the researchers for doing further research and practitioners to select among different choices. The code used for experimental comparison is released at: \url{//github.com/shivram1987/ActivationFunctions}.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191