Search
Search results for: APPROXIMATION THEORY
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublicationWe consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...
-
Neural Approximators for Variable-Order Fractional Calculus Operators (VO-FC)
PublicationThe paper presents research on the approximation of variable-order fractional operators by recurrent neural networks. The research focuses on two basic variable-order fractional operators, i.e., integrator and differentiator. The study includes variations of the order of each fractional operator. The recurrent neural network architecture based on GRU (Gated Recurrent Unit) cells functioned as a neural approximation for selected...
-
Domain segmentation for low-cost surrogate-assisted multi-objective design optimisation of antennas
PublicationAbstract: Information regarding the best possible design trade-offs of an antenna structure can be obtained through multiobjective optimisation (MO). Unfortunately, MO is extremely challenging if full-wave electromagnetic (EM) simulation models are used for performance evaluation. Yet, for the majority of contemporary antennas, EM analysis is the only tool that ensures reliability. This study introduces a procedure for accelerated...
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
Rothe’s method for physiologically structured models with diffusion
PublicationWe consider structured population models with diffusion and dynamic boundary conditions. The respective approximation, called Rothe’s method, produces positive and exponentially bounded solutions. Its solutions converge to the exact solution of the original PDE.
-
Gas sensors based on conducting polymers-recent developments
PublicationThis work discusses sensing performance dependence of PEDOT polymer and its composites on the counter ions used in the polymerization process. The sensors based on PEDOT-RGO composite show reversible response to NO2, while on PEDOT/LiClO4 irreversible. As a result, PEDOT-RGO could be used as a typical gas sensor, while sensor based PEDOT/LiClO4 could be used as an integrating gas sensor, also known as an accumulating gas sensor....
-
Application of regularized Savitzky–Golay filters to identification of time-varying systems
PublicationSavitzky–Golay (SG) filtering is a classical signal smoothing technique based on the local least squares approximation of the analyzed signal by a linear combination of known functions of time (originally — powers of time, which corresponds to polynomial approximation). It is shown that the regularized version of the SG algorithm can be successfully applied to identification of time-varying finite impulse response (FIR) systems....
-
Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublicationThe problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines...
-
Shared processor scheduling of multiprocessor jobs
PublicationWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Multi-objective design of miniaturized impedance transformers by domain segmentation
PublicationFast multi-objective design optimization of compact microstrip impedance transformers is discussed. Our approach exploits approximation models constructed using sampled coarse- mesh EM simulation data in a partitioned design space and response correction techniques for design refinement. Demonstra
-
Combined spline wavelet decomposition for 3d seafloor imaging from multibeam sonar echoes
PublicationThe paper proposes combined spline-wavelet approach to the raw echoes seaflor imaging from Multibeam Sonar System (MBSS) records. Wavelet representation is closely related to image representation, due to its unique approximations properties. Splines have the best approximation properties among all known wavelets of a given order, so they are best suited for approximating of smooth seafloor surface. Additionaly, wavelet bases have...
-
Proximal primal–dual best approximation algorithm with memory
PublicationWe propose a new modified primal–dual proximal best approximation method for solving convex not necessarily differentiable optimization problems. The novelty of the method relies on introducing memory by taking into account iterates computed in previous steps in the formulas defining current iterate. To this end we consider projections onto intersections of halfspaces generated on the basis of the current as well as the previous...
-
Method of lines for physiologically structured models with diffusion
PublicationWe deal with a size-structured model with diffusion. Partial differential equations are approximated by a large system of ordinary differential equations. Due to a maximum principle for this approximation method its solutions preserve positivity and boundedness. We formulate theorems on stability of the method of lines and provide suitable numerical experiments.
-
Text-mining Similarity Approximation Operators for Opinion Mining in BI tools
PublicationThe concept of the Text-mining Similarity Approximation Operators for Opinion Mining as extensions to Natural Language Interface Database is defined. The new operators: “keywords of” dimension; subsetting operator “about C is q”; aggregation operator “by similar C” are proposed. These operators are based on the Latent Semantic Analysis and Social Network Analysis
-
Cost-efficient multi-objective design optimization of antennas in highly-dimensional parameter spaces
PublicationMulti-objective optimization of antenna structures in highly-dimensional parameter spaces is investigated. For expedited design, variable-fidelity EM simulations and domain patching algorithm are utilized. The results obtained for a monopole antenna with 13 geometry parameters are compared with surrogate-assisted optimization involving response surface approximation modeling.
-
On the Structure of Time in Computational Semantics of a Variable-Step Solver for Hybrid Behavior Analysis
PublicationHybrid dynamic systems combine continuous and discrete behavior. Often, computational approaches are employed to derive behaviors that approximate the analytic solution. An important part of this is the approximation of differential equation behavior by numerical integration. The accuracy and computational efficiency of the integration usually depend on the complexity of the method and its implicated approximation errors, especially...
-
Pareto Ranking Bisection Algorithm for EM-Driven Multi-Objective Design of Antennas in Highly-Dimensional Parameter Spaces
PublicationA deterministic technique for fast surrogate-assisted multi-objective design optimization of antennas in highly-dimensional parameters spaces has been discussed. In this two-stage approach, the initial approximation of the Pareto set representing the best compromise between conflicting objectives is obtained using a bisection algorithm which finds new Pareto-optimal designs by dividing the line segments interconnecting previously...
-
An objective isogeometric mixed finite element formulation for nonlinear elastodynamic beams with incompatible warping strains
PublicationWe present a stable mixed isogeometric finite element formulation for geometrically and materially nonlinear beams in transient elastodynamics, where a Cosserat beam formulation with extensible directors is used. The extensible directors yield a linear configuration space incorporating constant in-plane cross-sectional strains. Higher-order (incompatible) strains are introduced to correct stiffness, whose additional degrees of...
-
Laboratory Determination of Burger's Model Parameters for Visco-elastic Analysis of Road Pavement Materials
PublicationBurger's Model is one of those models that describes performance of asphalt mixtures. Its parameters can be used in road construction analysis based on visco-elastic properties in wide variety of temperatures using dedicated programs (e.g. Veroad) or in Finite Element Method (FEM). Parameters of Burger's Model can be used for example in prediction of low temperature cracking in low winter temperatures or permanent deformation...
-
Fundamentals of Physics-Based Surrogate Modeling
PublicationChapter 1 was focused on data-driven (or approximation-based) modeling methods. The second major class of surrogates are physics-based models outlined in this chapter. Although they are not as popular, their importance is growing because of the challenges related to construction and handling of approximation surrogates for many real-world problems. The high cost of evaluating computational models, nonlinearity of system responses,...
-
A Simplified Method of Trend Removal to Determine Noise Observed During a Supercapacitor’s Discharging
PublicationIn this paper, new method of trend removal is proposed. This is a simplified method based on Empirical Mode Decomposition (EMD). The method was applied for voltage time series observed during supercapacitor discharging process. It assured the determination of an additive noise component after subtracting the identified trend component. We analyzed voltage time series observed between the terminals of the supercapacitor when discharged...
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm
PublicationWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm.
PublicationWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
Efficacy of modal curvature damage detection in various pre-damage data assumptions and modal identification techniques
PublicationThe efficacy of modal curvature approach for damage localization is discussed in the paper in the context of input data. Three modal identification methods, i.e., Eigensystem Realization Algorithm (ERA), Natural Excitation Technique with ERA (NExT-ERA) and Covariance Driven Stochastic Subspace Identification (SSI-Cov), and four methods of determining baseline data, i.e., real measurement of the undamaged state, analytical function,...
-
Design Space Reduction for Expedited Multi-Objective Design Optimization of Antennas in Highly-Dimensional Spaces
PublicationA surrogate-based technique for efficient multi-objective antenna optimization is discussed. Our approach exploits response surface approximation (RSA) model constructed from low-fidelity antenna model data (here, obtained through coarse-discretization electromagnetic simulations). The RSA model enables fast determination of the best available trade-offs between conflicting design goals. The cost of RSA model construction for multi-parameter...
-
Reduced-Cost Constrained Modeling of Microwave and Antenna Components: Recent Advances
PublicationElectromagnetic (EM) simulation models are ubiquitous in the design of microwave and antenna components. EM analysis is reliable but CPU intensive. In particular, multiple simulations entailed by parametric optimization or uncertainty quantification may considerably slow down the design processes. In order to address this problem, it is possible to employ fast metamodels. Here, the popular solution approaches are approximation...
-
Pressure effects on the electronic structure and superconductivity of (TaNb)0.67(HfZrTi)0.33 high entropy alloy
PublicationEffects of pressure on the electronic structure, electron-phonon interaction, and superconductivity of the high entropy alloy ( TaNb ) 0.67 ( HfZrTi ) 0.33 are studied in the pressure range 0–100 GPa. The electronic structure is calculated using the Korringa-Kohn-Rostoker method with the coherent potential approximation. Effects of pressure on the lattice dynamics are simulated using the Debye-Grüneisen model and the Grüneisen...
-
On Bayesian Tracking and Prediction of Radar Cross Section
PublicationWe consider the problem of Bayesian tracking of radar cross section. The adopted observation model employs the gamma family, which covers all Swerling cases in a unified framework. State dynamics are modeled using a nonstationary autoregressive gamma process. The principal component of the proposed solution is a nontrivial gamma approximation, applied during the time update recursion. The superior performance of the proposed approach...
-
Fast Basis Function Estimators for Identification of Nonstationary Stochastic Processes
PublicationThe problem of identification of a linear nonsta-tionary stochastic process is considered and solved using theapproach based on functional series approximation of time-varying parameter trajectories. The proposed fast basis func-tion estimators are computationally attractive and yield resultsthat are better than those provided by the local least squaresalgorithms. It is shown that two...
-
Residue-Pole Methods for Variability Analysis of S-parameters of Microwave Devices with 3D FEM and Mesh Deformation
PublicationThis paper presents a new approach for variability analysis of microwave devices with a high dimension of uncertain parameters. The proposed technique is based on modeling an approximation of system by its poles and residues using several modeling methods, including ordinary kriging, Adaptive Polynomial Chaos (APCE), and Support Vector Machine Regression (SVM). The computational cost is compared with the traditional Monte-Carlo...
-
FIR Filter Design Using Distributed Maximal Flatness Method
PublicationIn the paper a novel method for filter design based on the distributed maximal flatness method is presented. The proposed approach is based on the method used to design the most common FIR fractional delay filter - the maximally flat filter. The MF filter demonstrates excellent performance but only in a relatively narrow frequency range around zero frequency but its magnitude response is no greater than one. This ,,passiveness”...
-
Trust Dynamics Analysis of CTR Scheme Subversion under Virtual Anonymity and Trust-Unaware Partner Selection
PublicationWe propose a framework to study Markovian trust value dynamics in a centralized Computational Trust and Reputation (CTR) scheme under trust-unaware partner selection using a mean-value approximation. Analytically founded answers are sought to questions like: Can dishonest agents subvert the CTR scheme (i.e., acquire higher trust values than honest agents)? Is indirect reciprocity incentivized? Is there a qualitative impact of a...
-
Locating and Identifying Ferromagnetic Objects
PublicationThe new non-iterative method of determining the dipole moment and location is presented in this paper. The algorithm of an object's localization and identification was achieved by using numerical calculations and approximation method. The arbitrary shapes of an object were assumed in the identification algorithm - axially symmetric spheroid (a prolate and an oblate). Several examples of localization and identification of an object's...
-
A Method for Optimising the Blade Profile in Kaplan Turbine
PublicationThis paper introduces a method of blade profile optimisation for Kaplan-type turbines, based on modelling the interaction between rotor and stator blades. Rotor and stator blade geometry is described mathematically by means of a midline curve and thickness distribution. Genetic algorithms are then used to find a global optimum that minimises the loss coefficient. This allows for variety of possible blade shapes and configurations....
-
Locating and Identifying Ferromagnetic Objects
PublicationThe new non-iterative method of determining the dipole moment and location is presented in this paper. The algorithm of an object's localization and identification was achieved by using numerical calculations and approximation method. The arbitrary shapes of an object were assumed in the identification algorithm - axially symmetric spheroid (a prolate and an oblate). Several examples of localization and identification of an object's...
-
Contextualizing a Knowledge Base by Approximation – A Case Study
PublicationModular knowledge bases give their users opportunity to store and access knowledge at different levels of generality. In this paper we present how to organize a modular knowledge bases organized into contexts in which a user can express their knowledge in much simplified way, yet without losing its precision. The work is centered around the notion of approximation - i.e. reducing the arity of predicates used. The presentation is...
-
Response features for fast EM-driven design of miniaturized impedance matching transformers
PublicationA framework for low-cost EM-driven design optimization of compact impedance matching transformers is presented. Our technique is based on a bottom-up design where design requirements for the transformer circuit are translated into specifications for its building blocks. These elementary cells are optimized using response features. Subsequently, the entire circuit is fine-tuned using local response surface approximation models and...
-
Errors of a Linear Current Approximation in High-Speed PMSM Drives
PublicationCurrent sampling techniques and predictive algorithms used in the digital control of electric drives rely on a simple mathematical model that assumes linear current changes upon constant supplying voltages. This paper identifies rotor movement as a factor that makes this assumption invalid when the rotor covers an angular distance of a few tens of degrees during the control interval duration. The errors of the linear current approximation...
-
A Simulative Comparison of Ship Domains and Their Polygonal Approximations
PublicationThe paper investigates the impact of a precise ship domain shape on the size of collision avoidance manoeuvres. The considered collision avoidance manoeuvres include both course and speed alterations. Various ship domains are compared with their polygonal approximations, which vary in the number of points of a domain contour and placement of these points. The best of all considered approximations is determined in the course of...
-
Elastic scattering of electrons from chloroform
PublicationWe present experimental and theoretical cross sections for elastic electron scattering from CHCl3. This is an important target because of its relevance to environmental chemistry and the plasma etching industry as a source of chlorine radicals. The experimental results were obtained at incident electron energies ranging from 0.5 to 800 eV in the 10deg-130deg scattering angle range. Theoretically, the scattering cross sections in...
-
Cavity-expansion approximation for projectile impact and penetration into sand
PublicationA one-dimensional problem of a spherical cavity expanding at a constant velocity from zero initial radius in an infinite granular medium, which has the first-kind self-similar solution, is considered. We are solving this dynamic spherical cavity-expansion problem to model rigid spheres penetrating into a granular media. Elastic–plastic deformation of the granular media is described in a barotropic approximation, using the high-pressure...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublicationIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...
-
Fast Multi-Objective Antenna Design Through Variable-Fidelity EM Simulations
PublicationA technique for fast multi-objective antenna optimization is introduced. A kriging interpolation surrogate constructed from sampled coarse-mesh EM simulations is utilized by multi-objective evolutionary algorithm (MOEA) to obtain the initial Pareto front approximation. The surrogate is defined in a subset of the original design space, determined by means of independently optimized individual objectives. Response correction techniques...
-
Variable-fidelity shape optimization of dual-rotor wind turbines
PublicationPurpose Dual-rotor wind turbines (DRWTs) are a novel type of wind turbines that can capture more power than their single-rotor counterparts. Because their surrounding flow fields are complex, evaluating a DRWT design requires accurate predictive simulations, which incur high computational costs. Currently, there does not exist a design optimization framework for DRWTs. Since the design optimization of DRWTs requires numerous model...
-
Strategies for computationally feasible multi-objective simulation-driven design of compact RF/microwave components
PublicationMulti-objective optimization is indispensable when possible trade-offs between various (and usually conflicting) design objectives are to be found. Identification of such design alternatives becomes very challenging when performance evaluation of the structure/system at hand is computationally expensive. Compact RF and microwave components are representative examples of such a situation: due to highly compressed layouts and considerable...
-
Local basis function estimators for identification of nonstationary systems
PublicationThe problem of identification of a nonstationary stochastic system is considered and solved using local basis function approximation of system parameter trajectories. Unlike the classical basis function approach, which yields parameter estimates in the entire analysis interval, the proposed new identification procedure is operated in a sliding window mode and provides a sequence of point (rather than interval) estimates. It is...
-
Active Dynamic Thermography imaging of wound healing processes in cardio surgery
PublicationThe surgery is a branch of medicine, that is integrally connected to wounds. Despite using sterile tools and compliance with aseptic rolls, some of the surgery wounds become infected. In clinical practice there is a lack of cheap, objective methods and tools for quantitative definition and estimation of the surgery wound healing progress. This paper presents preliminary results of Active Dynamic Thermography (ADT) parametric imaging...
-
Depth Determination Accuracy of the Modified Prony Method in a Swath Mapping Application
PublicationThis article presents the performance of the modified Prony method in a swath mapping application. Depth determination accuracy is assessed by processing raw signal acquired by an EdgeTech 6205 swath bathymetry system over flat seafloor. An updated version of the method, proposed previously by the authors, is used to determine the number of signal echoes. The number of signal echoes is essential for performing the low-rank approximation...
-
Using Wearable Electronics to Estimate Usefulness of Heart Rate Variability for Bathing Person Identif Cation
PublicationIn this paper the possibility of person identification based on biosignal is investigated. The work focus on the analysis of the changes in intervals between successive R-waves of electrocardiogram (ECG) recorded by wearable electronics in form of a necklaces. The main idea behind this project is to find efficient tool which may prevent sudden consciousness loss episodes or even sudden death episodes related to rapid temperature...
-
Approximate solution for Euler equations of stratified water via numerical solution of coupled KdV system
PublicationWe consider Euler equations with stratified background state that is valid for internal water waves. The solution of the initial-boundary problem for Boussinesq approximation in the waveguide mode is presented in terms of the stream function. The orthogonal eigenfunctions describe a vertical shape of the internal wave modes and satisfy a Sturm-Liouville problem. The horizontal profile is defined by a coupled KdV system which is...