Data‐driven execution of fast multipole methods

Fast multipole methods (FMMs) have complexity, are compute bound, and require very little synchronization, which makes them a favorable algorithm on next‐generation supercomputers. Their most common application is to accelerate N‐body problems, but they can also be used to solve boundary integral equations. When the particle distribution is irregular and the tree structure is adaptive, load balancing becomes a non‐trivial question. A common strategy for load balancing FMMs is to use the work load from the previous step as weights to statically repartition the next step. The authors discuss in the paper another approach based on data‐driven execution to efficiently tackle this challenging load balancing problem. The core idea consists of breaking the most time‐consuming stages of the FMMs into smaller tasks. The algorithm can then be represented as a directed acyclic graph where nodes represent tasks and edges represent dependencies among them. The execution of the algorithm is performed by asynchronously scheduling the tasks using the queueing and runtime for kernels runtime environment, in a way such that data dependencies are not violated for numerical correctness purposes. This asynchronous scheduling results in an out‐of‐order execution. The performance results of the data‐driven FMM execution outperform the previous strategy and show linear speedup on a quad‐socket quad‐core Intel Xeon system.Copyright © 2013 John Wiley & Sons, Ltd.     

An efficient solution to the subset‐sum problem on GPU

We present an algorithm to solve the subset‐sum problem (SSP) of capacity c and n items with weights w_i,1≤i≤n, spending O(n(m − w_min)/p) time and O(n + m − w_min) space in the Concurrent Read/Concurrent Write (CRCW) PRAM model with 1≤p≤m − w_min processors, where w_min is the lowest weight and , improving both upper‐bounds. Thus, when n≤c, it is possible to solve the SSP in O(n) time in parallel environments with low memory. We also show OpenMP and CUDA implementations of this algorithm and, on Graphics Processing Unit, we obtained better performance than the best sequential and parallel algorithms known so far. Copyright © 2015 John Wiley & Sons, Ltd.     

Bit duplication technique to generate hard quadratic unconstrained binary optimization problems with adjustable sizes

Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with $n$ bits is converted to a hard QUBO problem with $(m+n)$ bits . We use random QUBO problems, N-Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave samplers with SA, D-Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.     

A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem

The efficiency of metaheuristic algorithms depends significantly on the number of fitness value evaluations performed on candidate solutions. In addition to various intelligent techniques used to obtain better results, parallelization of calculations can substantially improve the solutions in cases where the problem is NP-hard and requires many evaluations. This study proposes a new parallel tabu search method for solving the Maximum Vertex Weight Clique Problem (MVWCP) on the Non-Uniform Memory Access (NUMA) architectures using the OpenMP parallel programming paradigm. Achieving scalability in the NUMA architectures presents significant challenges due to the high complexity of their memory systems, which can lead to performance loss. However, our proposed Tabu-NUMA algorithm provides up to $18\times$ speed-up with 64 cores for ten basic problem instances in DIMACS-W and BHOSLIB-W benchmarks. And it improves the performance of the serial Multi Neighborhood Tabu Search (MN/TS) algorithm for 38 problem instances in DIMACS-W and BHOSLIB-W benchmarks. We further evaluate our algorithm on larger datasets with thousands of edges and vertices from Network Data Repository benchmark problem instances, and we report significant improvements in terms of speed up. Our results confirm that the Tabu-NUMA algorithm is among the best recent algorithms for solving MVWCP on the NUMA architectures.     

Smart admission control strategy utilizing volunteer-enabled fog-cloud computing

Fog computing has become an effective platform for computing delay-sensitive IoT tasks. However, the increased scalability of IoT devices ( $\mathrm{IDs}$) makes it difficult for fog nodes to perform better. Volunteer computing (VC) has emerged as a supportive technology in which resource-capable $\mathrm{ID}$s, such as computers and laptops, share their idle resources to compute the IoT tasks. However, in VC-based approaches, improper selection of volunteer nodes (VNs) may result in an increased failure rate and delay. To address these challenges, this work proposes a Smart Admission Control strategy utilizing volunteer-enabled Fog-Cloud computing (SAC-VFC). The VNs are selected based on grey TOPSIS ranking. The incoming tasks are classified based on priority and delay and then scheduled using the Improved Jellyfish Algorithm (IJFA). Smart gateway (SGW) and fog manager (FM) act as mediators for allocating tasks among voluntary, fog, and cloud resources. FM performs a similarity-based clustering of fog nodes using the enhanced Fuzzy C Means clustering (EFCM) algorithm to manage resources. Simulation study suggests the superior performance of SAC-VFC over peers under comparison in terms of average delay, average makespan, success rate of tasks and tasks satisfying the deadline metrics.     

Identification of influential vertices in complex networks: A hitting time-based approach

Unravelling the dynamics of network vertices is pivotal, and traditional centrality measures have limitations in adapting to structural changes, directed and weighted networks, and temporal analyses. This paper introduces a ground breaking approach - hitting time-based centrality. Utilizing network matrix notations and a random walk model on a connected network , we establish a Markov chain to quantify the hitting time, hitting distance, and hitting centrality, providing a nuanced measure prioritizing central vertices. Through extensive experiments using Kendall's tau coefficient, the paper evaluates the method's correlation with actual influence in the Susceptible-Infectious (SI) model, showcasing superior performance across diverse network sizes and structures. The hitting centrality method exhibits sensitivity to connectivity dynamics, effective incorporation of temporal dynamics, and robust handling of weighted and directed networks. Positive Kendall's tau coefficients underline the method's proficiency in prioritizing influential vertices by correlating hitting centrality values with actual infection ability. The demonstrated robustness to structural changes enhances its utility for dynamic network analysis. In conclusion, our hitting time-based centrality approach emerges as a promising method, mitigating the shortcomings of traditional measures. By integrating information propagation speed, accommodating network dynamics, and enabling time-dependent analyses, it offers a comprehensive tool for evaluating vertex importance and influence in complex networks.     

An LMI approach to robust fault estimation for a class of nonlinear systems

The paper presents a robust fault estimation approach for a class of nonlinear discrete‐time systems. In particular, two sources of uncertainty are present in the considered class of systems, that is, an unknown input and an exogenous external disturbance. Thus, apart from simultaneous state and fault estimation, the objective is to decouple the effect of an unknown input while minimizing the influence of the exogenous external disturbance within the framework. The resulting design procedure guarantees that a prescribed disturbance attenuation level is achieved with respect to the state and fault estimation error while assuring the convergence of the observer. The core advantage of the proposed approach is its simplicity by reducing the fault estimation problem to matrix inequalities formulation. In addition, the design conditions ensure the convergence of the observer with guaranteed performance. The effectiveness of the proposed approach is demonstrated by its application to a twin rotor multiple‐input multiple‐output system. Copyright © 2015 John Wiley & Sons, Ltd.     

New interpolation solution and application in system modeling and optimal control with prescribed distance to instability

We present a system theoretic interpretation of a two‐sided interpolation problem with a stable rational matrix U (interpolant) without constraints on its norm. It is known that all solutions U of that problem can be expressed as U = U _h+ U _p, where U _h ranges in the set of all solutions of the associated homogeneous problem, and U _p is a particular solution. We present a new solution for U _p and prove that it is actually the minimal ‐norm interpolant in the set of all interpolants. We apply these results in system modeling and in optimal control of one‐block plants, with a prescribed bound on the distance to instability of the closed‐loop system. The applications are illustrated by examples. Interesting connections to the augmented basic interpolation problem, to Nehari's problem, and to the stability of one‐block plants with multiple unstable invariant zeros are given. Copyright © 2015 John Wiley & Sons, Ltd.     

Controllability of Semilinear Systems of Parabolic Equations with Delay on the State

In this paper we prove the approximate controllability of the following semilinear system parabolic equations with delay on the state variable where Ω is a bounded domain in is a n × n non diagonal matrix whose eigenvalues are semi‐simple with non negative real part, the control u belongs to and B is a n × m matrix. Here τ≥0 is the maximum delay, which is supposed to be finite. We assume that the operator L:L²([?τ,0];Z)→Z is linear and bounded with and the nonlinear function f:[0,r] × IRⁿ×IR^m→IRⁿ is smooth and bounded.     

Quantized filtering for Markovian jump LPV systems with intermittent measurements

This paper investigates the problem of quantized filtering for a class of discrete‐time linear parameter‐varying systems with Markovian switching under data missing. The measured output of the plant is quantized by a logarithmic mode‐independent quantizer. The data missing phenomenon is modeled by a stochastic variable. The purpose of the problem addressed is to design a full‐order filter such that the filtering error dynamics is stochastically stable and the prescribed noise attenuation level in the sense can be achieved. Sufficient conditions are derived for the existence of such filters in terms of parameterized linear matrix inequalities. Then the corresponding filter synthesis problem is transformed into a convex optimization problem that can be efficiently solved by using standard software packages. A simulation example is utilized to demonstrate the usefulness of the developed theoretical results. Copyright © 2011 John Wiley & Sons, Ltd.     

Thin‐slot formalism for the split‐field FDTD analysis of periodic structure

An expression of the thin‐slot formalism is presented to alleviate the gridding of the split‐field finite‐difference time‐domain (FDTD) solution for periodic structure. The varying auxiliary‐field ( , ) and split‐field ( , ) distributions near the slots are analytically derived from the varying field ( , ). The update equations for the split‐field FDTD are obtained by incorporating those varying field distributions into the split‐field equations in integral form. A frequency selective surface (FSS) structure is applied to verify the proposed method. The results indicate that the computational efficiency is improved.     

Another view on q‐rung orthopair fuzzy sets

In this paper, two new approaches have been presented to view q‐rung orthopair fuzzy sets. In the first approach, these can viewed as L‐fuzzy sets, whereas the second approach is based on the notion of orbits. Uncertainty index is the quantity , which remains constant for all points in an orbit. Certain operators can be defined in q‐ROF sets, which affect when applied to some q‐ROF sets. Operators , , and have been defined. It is studied that how these operators affect when applied to some q‐ROF set A.     

Dissipativity‐based asynchronous control of discrete‐time Markov jump systems with mixed time delays

This paper addresses the problem of dissipativity‐based asynchronous control for a class of discrete‐time Markov jump systems. A unified framework to design a controller for discrete‐time Markov jump systems with mixed time delays is proposed, which is fairly general and can be reduced to a synchronous controller or a mode‐independent controller. Based on a stochastic Lyapunov function approach, which fully utilizes available information of the system mode and the controller, a sufficient condition is established to ensure the stochastic stability and strictly ( , , ) dissipative performance of the resulting closed‐loop system. Finally, the effectiveness and validity of the proposed method are illustrated with a simulation example.     

Laplace–Beltrami Operator on Point Clouds Based on Anisotropic Voronoi Diagram

The symmetrizable and converged Laplace–Beltrami operator () is an indispensable tool for spectral geometrical analysis of point clouds. The , introduced by Liu et al. [LPG12] is guaranteed to be symmetrizable, but its convergence degrades when it is applied to models with sharp features. In this paper, we propose a novel , which is not only symmetrizable but also can handle the point‐sampled surface containing significant sharp features. By constructing the anisotropic Voronoi diagram in the local tangential space, the can be well constructed for any given point. To compute the area of anisotropic Voronoi cell, we introduce an efficient approximation by projecting the cell to the local tangent plane and have proved its convergence. We present numerical experiments that clearly demonstrate the robustness and efficiency of the proposed for point clouds that may contain noise, outliers, and non‐uniformities in thickness and spacing. Moreover, we can show that its spectrum is more accurate than the ones from existing for scan points or surfaces with sharp features.     

Input‐output triggered control using ‐stability over finite horizons

This paper investigates stability of nonlinear control systems under intermittent information. Following recent results in the literature, we replace the traditional periodic paradigm, where the up‐to‐date information is transmitted and control laws are executed in a periodic fashion, with the event‐triggered paradigm. Building on the small gain theorem, we develop input–output triggered control algorithms yielding stable closed‐loop systems. In other words, based on the currently available (but outdated) measurements of the outputs and external inputs of a plant, a mechanism triggering when to obtain new measurements and update the control inputs is provided. Depending on the noise in the environment, the developed algorithm yields stable, asymptotically stable, and ‐stable (with bias) closed‐loop systems. Control loops are modeled as interconnections of hybrid systems for which novel results on ‐stability are presented. The prediction of a triggering event is achieved by employing ‐gains over a finite horizon. By resorting to convex programming, a method to compute ‐gains over a finite horizon is devised. Finally, our approach is successfully applied to a trajectory tracking problem for unicycles. Copyright © 2014 John Wiley & Sons, Ltd.     

New results on stability of singular stochastic Markov jump systems with state‐dependent noise

This paper aims to develop the stability theory for singular stochastic Markov jump systems with state‐dependent noise, including both continuous‐time and discrete‐time cases. The sufficient conditions for the existence and uniqueness of a solution to the system equation are provided. Some new and fundamental concepts such as non‐impulsiveness and mean square admissibility are introduced, which are different from those of other existing works. By making use of the ‐representation technique and the pseudo inverse E⁺ of a singular matrix E, sufficient conditions ensuring the system to be mean square admissible are established in terms of strict linear matrix inequalities, which can be regarded as extensions of the corresponding results of deterministic singular systems and normal stochastic systems. Practical examples are given to demonstrate the effectiveness of the proposed approaches. Copyright © 2015 John Wiley & Sons, Ltd.     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

Spline Based Pseudo‐Inversion of Sampled Data Non‐Minimum Phase Systems for an Almost Exact Output Tracking

This paper considers the problem of achieving a very accurate tracking of a pre‐specified desired output trajectory , for linear, multiple input multiple output, non‐minimum phase and/or non hyperbolic, sampled data, and closed loop control systems. The proposed approach is situated in the general framework of model stable inversion and introduces significant novelties with the purpose of reducing some theoretical and numerical limitations inherent in the methods usually proposed. In particular, the new method does not require either a preactuation or null initial conditions of the system. The desired and the corresponding sought input are partitioned in a transient component ( and u_t(k), respectively) and steady‐state ( and u_s(k), respectively). The desired transient component is freely assigned without requiring it to be null over an initial time interval. This drastically reduces the total settling time. The structure of u_t(k) is a priori assumed to be given by a sampled smoothing spline function. The spline coefficients are determined as the least‐squares solution of the over‐determined system of linear equations obtained imposing that the sampled spline function assumed as reference input yield the desired output over a properly defined transient interval. The steady‐state input u_s(k) is directly analytically computed exploiting the steady‐state output response expressions for inputs belonging to the same set of .     

A coaxial probe fed wideband circularly polarized antenna using unequal and adjacent‐slided rectangular dielectric resonators for WLAN applications

In this article, a coaxial probe fed wideband circularly polarized antenna has been designed and investigated using unequal and adjacent‐slided rectangular dielectric resonators radiating in broadside direction (Φ = 0°, θ = 0°). Wi‐Fi wireless network use radio signal either in 2.4 or 5 GHz band. Owing to high rush in 2.4 GHz band, the proposed antenna is designed for 5 GHz (5.15‐5.825 GHz) WLAN band. The proposed design uses fundamental orthogonal modes and excited in two individual rectangular dielectric resonators to achieve wide axial‐ratio bandwidth (below 3 dB). Measured input reflection coefficient (below ?10 dB) and axial ratio bandwidth (below 3 dB) of 26.07% (5.27‐6.85 GHz) and 26.85% (5.32‐6.97 GHz) has been attained, respectively, in this proposed antenna. The measured far‐field patterns such as gain and radiation patterns are showing consistent performance throughout the working band.