Search
Search results for: Computational complexity
-
COMPUTATIONAL COMPLEXITY
Journals -
ANALYSIS OF EFFECTIVENESS AND COMPUTATIONAL COMPLEXITY OF TREND REMOVAL METHODS
PublicationThe paper presents a method of processing measurement data due to remove slowly varying component of the trend occurring in the recorded waveforms. Comparison of computational complexity and trend removal efficiency between some commonly used methods is presented. The impact of these procedures on probability distribution and power spectral density is shown. Effectiveness and computational complexity of these methods depend essentially...
-
Reduction of Computational Complexity in Simulations of the Flow Process in Transmission Pipelines
PublicationThe paper addresses the problem of computational efficiency of the pipe-flow model used in leak detection and identification systems. Analysis of the model brings attention to its specific structure, where all matrices are sparse. With certain rearrangements, the model can be reduced to a set of equations with tridiagonal matrices. Such equations can be solved using the Thomas algorithm. This method provides almost the same values...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.
-
Computational Complexity and Its Influence on Predictive Capabilities of Machine Learning Models for Concrete Mix Design
PublicationThe design of concrete mixtures is crucial in concrete technology, aiming to produce concrete that meets specific quality and performance criteria. Modern standards require not only strength but also eco-friendliness and production efficiency. Based on the Three Equation Method, conventional mix design methods involve analytical and laboratory procedures but are insufficient for contemporary concrete technology, leading to overengineering...
-
Computational complexity and length of recorded data for fluctuation enhanced sensing method in resistive gas sensors
PublicationThis paper considers complexity and accuracy of data processing for gas detection using resistance fluctuation data observed in resistance gas sensors. A few selected methods were considered (Principal Component Analysis – PCA, Support Vector Machine – SVM). Functions like power spectral density or histogram were used to create input data vector for these algorithms from the observed resistance fluctuations. The presented considerations...
-
IEEE Conference on Computational Complexity
Conferences -
The chapter analyses the K-Means algorithm in its parallel setting. We provide detailed description of the algorithm as well as the way we paralellize the computations. We identified complexity of the particular steps of the algorithm that allows us to build the algorithm model in MERPSYS system. The simulations with the MERPSYS have been performed for different size of the data as well as for different number of the processors used for the computations. The results we got using the model have been compared to the results obtained from real computational environment.
PublicationThe chapter analyses the K-Means algorithm in its parallel setting. We provide detailed description of the algorithm as well as the way we paralellize the computations. We identified complexity of the particular steps of the algorithm that allows us to build the algorithm model in MERPSYS system. The simulations with the MERPSYS have been performed for different size of the data as well as for different number of the processors used...
-
Marek Kubale prof. dr hab. inż.
PeopleDetails concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...
-
Complexity Issues on of Secondary Domination Number
PublicationIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
Michał Małafiejski dr hab. inż.
PeopleMichał Małafiejski was born in 1975. He received the M.Sc. in computer science (in 1999). He received the Ph.D. in computer science in 2002 and habilitation in the same area in 2014. He works as associate professor in Department of Algorithms and Modelling of Systems. He is the author or coauthor of many papers related to theoretrical computer science. Main area of his research is the design of efficient algorithms and the analysis...
-
The Complexity of Zero-Visibility Cops and Robber
PublicationIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
Source code - AI models (MLM1-5 - series I-III - QNM opt)
Open Research DataSource code - AI models (MLM1-5 - series I-III - QNM opt) for the paper "Computational Complexity and Its Influence on Concrete Compressive Strength Prediction Capabilities of Machine Learning Models for Concrete Mix Design Support" accepted for publication.
-
The complexity of zero-visibility cops and robber
PublicationWe consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...
-
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
Joanna Raczek dr inż.
PeopleEmployment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...
-
Complexity analysis of the Pawlak’s flowgraph extension for re-identification in multi-camera surveillance system
PublicationThe idea of Pawlak’s flowgraph turned out to be a useful and convenient container for a knowledge of objects’ behaviour and movements within the area observed with a multi-camera surveillance system. Utilization of the flowgraph for modelling behaviour admittedly requires certain extensions and enhancements, but it allows for combining many rules into a one data structure and for obtaining parameters describing how objects tend...
-
Sample Rate Conversion Based on Frequency Response Masking Filter
PublicationThe sample rate conversion with high resampling ratios requires low-pass digital filters with very narrow transition band which results in high computational complexity and makes filter design problematic. Therefore in this work we propose to use the FRM method, which breaks the filter with a narrow transition band into a group of filters with reduced design requirements. These decreases the number of non-zero coefficients and...
-
Modeling of Performance, Reliability and Energy Efficiency in Large-Scale Computational Environment
PublicationLarge scale of complexity of distributed computational systems imposes special challanges for prediction of quality in such systems.Existing quality models for lower-scale systems include functionality,performance,reliability,flexibility and usability.Among these attributes,performance and reliability have a particular significance to the large-scale systems computing quality modeling due to their strong dependence on the system...
-
Modeling of Performance, Reliability and Energy Efficiency in Large-Scale Computational Environments
PublicationLarge scale of complexity of distributed computational systems imposes special challenges for prediction of quality in such systems. Existing quality models for lower-scale systems include functionality, performance, reliability, flexibility and usability. Among these attributes, performance and reliability have a particular significance to the large-scale systems computing quality modeling due to their strong dependence on the...
-
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...
-
A low complexity double-talk detector based on the signal envelope
PublicationA new algorithm for double-talk detection, intended for use in the acoustic echo canceller for voice communication applications, is proposed. The communication system developed by the authors required the use of a double-talk detection algorithm with low complexity and good accuracy. The authors propose an approach to doubletalk detection based on the signal envelopes. For each of three signals: the far-end speech, the microphone...
-
Direct spectrum detection based on Bayesian approach
PublicationThe paper investigates the Bayesian framework's performance for a direct detection of spectrum parameters from the compressive measurements. The reconstruction signal stage is eliminated in by the Bayesian Compressive Sensing algorithm, which causes that the computational complexity and processing time are extremely reduced. The computational efficiency of the presented procedure is significantly...
-
Interpolator wykorzystujący filtr z maskowaniem charakterystyki częstotliwościowej
PublicationInterpolator o dużej krotności wymaga stosowania dolnoprzepustowych filtrów cyfrowych o bardzo wąskim paśmie przejściowym. Przekłada się to na dużą złożoność obliczeniową i problemy z projektowaniem filtrów interpolacyjnych. W pracy zaproponowano użycie metody FRM rozbijającej filtr o wąskim paśmie przejściowym na grupę filtrów o obniżonych wymaganiach, co zmniejsza liczbę niezerowych współczynników. W rezultacie użycie tego rozwiązania...
-
Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
PublicationQuantum communication with systems of dimension larger than two provides advantages in information processing tasks. Examples include higher rates of key distribution and random number generation. The main disadvantage of using such multi-dimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a not-so-obvious problem: the relation between randomness certification and computational requirements...
-
Comparison and Analysis of Service Selection Algorithms
PublicationIn Service Oriented Architecture, applications are developed by integration of existing services in order to reduce development cost and time. The approach, however, requires algorithms that select appropriate services out of available, alternative ones. The selection process may consider both optimalization requirements, such as maximalization of performance, and constraint requirements, such minimal security or maximum development...
-
Feature Reduction Using Similarity Measure in Object Detector Learning with Haar-like Features
PublicationThis paper presents two methods of training complexity reduction by additional selection of features to check in object detector training task by AdaBoost training algorithm. In the first method, the features with weak performance at first weak classifier building process are reduced based on a list of features sorted by minimum weighted error. In the second method the feature similarity measures are used to throw away that features...
-
Real‐Time PPG Signal Conditioning with Long Short‐Term Memory (LSTM) Network for Wearable Devices
PublicationThis paper presents an algorithm for real‐time detection of the heart rate measured on a person’s wrist using a wearable device with a photoplethysmographic (PPG) sensor and accelerometer. The proposed algorithm consists of an appropriately trained LSTM network and the Time‐Domain Heart Rate (TDHR) algorithm for peak detection in the PPG waveform. The Long Short‐Term Memory (LSTM) network uses the signals from the accelerometer...
-
Computer-aided analysis of signals from a low-coherence Fabry-Perot interferometer used for measurements of biological samples
PublicationThe aim of the study was to develop an automated computer-aided system for analysis of spectrograms obtained from measurements of biological samples performed with a low-coherence Fabry-Pérot interferometer. Information necessary to determine dispersion characteristics of measured materials can be calculated from the positions of the maxima and minima that are present in their spectra. The main challenge faced during the development...
-
Diagnostic Models and Estimators for LDI in Transmission Pipelines
PublicationThis article considers and compares four analytical models of the pipeline flow process for leak detection and location tasks. The synthesis of these models is briefly outlined. Next, the methodology for generating data and diagnosing pipes is described, as well as experimental settings, assumptions and implemented scenarios. Finally, the quality of model-based diagnostic estimators has been evaluated for their bias, standard deviations...
-
Residual MobileNets
PublicationAs modern convolutional neural networks become increasingly deeper, they also become slower and require high computational resources beyond the capabilities of many mobile and embedded platforms. To address this challenge, much of the recent research has focused on reducing the model size and computational complexity. In this paper, we propose a novel residual depth-separable convolution block, which is an improvement of the basic...
-
Low-fidelity model considerations for simulation-based optimisation of miniaturised wideband antennas
PublicationHere, variable-fidelity electromagnetic (EM)-based design optimisation of miniaturised antennas is discussed. The authors focus on an appropriate selection of discretisation density of the low-fidelity EM model, which results in good performance of the optimisation algorithm in terms of its computational complexity and reliability. Trust-region gradient search with low-fidelity model corrected by means of non-linear frequency scaling...
-
Efficient Surrogate Modeling and Design Optimization of Compact Integrated On-Chip Inductors Based on Multi-Fidelity EM Simulation Models
PublicationHigh-performance and small-size on-chip inductors play a critical role in contemporary radio-frequency integrated circuits. This work presents a reliable surrogate modeling technique combining low-fidelity EM simulation models, response surface approximations based on kriging interpolation, and space mapping technology. The reported method is useful for the development of broadband and highly accurate data-driven models of integrated...
-
Interactive Query Expansion with the Use of Clustering by Directions Algorithm
PublicationThis paper concerns Clustering by Directions algorithm. The algorithm introduces a novel approach to interactive query expansion. It is designed to support users of search engines in forming web search queries. When a user executes a query, the algorithm shows potential directions in which the search can be continued. This paper describes the algorithm and it presents an enhancement which reduces the computational complexity of...
-
Local Texture Pattern Selection for Efficient Face Recognition and Tracking
PublicationThis paper describes the research aimed at finding the optimal configuration of the face recognition algorithm based on local texture descriptors (binary and ternary patterns). Since the identification module was supposed to be a part of the face tracking system developed for interactive wearable computer, proper feature selection, allowing for real-time operation, became particularly important. Our experiments showed that it is...
-
Optimization issues in distributed computing systems design
PublicationIn recent years, we observe a growing interest focused on distributed computing systems. Both industry and academia require increasing computational power to process and analyze large amount of data, including significant areas like analysis of medical data, earthquake, or weather forecast. Since distributed computing systems – similar to computer networks – are vulnerable to failures, survivability mechanisms are indispensable...
-
Performance Evaluation of Selected Parallel Object Detection and Tracking Algorithms on an Embedded GPU Platform
PublicationPerformance evaluation of selected complex video processing algorithms, implemented on a parallel, embedded GPU platform Tegra X1, is presented. Three algorithms were chosen for evaluation: a GMM-based object detection algorithm, a particle filter tracking algorithm and an optical flow based algorithm devoted to people counting in a crowd flow. The choice of these algorithms was based on their computational complexity and parallel...
-
Using Alpha-beta filtration for robustness improvement of a quadrocopter positioning system
PublicationQuadrocopter is an unmanned aerial vehicle (UAV) platform. The position of the robot is determined based on readings from an accelerometer and a gyroscope, but the measurement signals contain broadband noise. This article describes a solution for filtering out the noise based on an Alpha – beta filter. It also presents the methodology of designing and implementing such a filter for noise cancellation in measurement signals from...
-
Improvement of time difference of arrival measurements resolution by using fractional delay filters in a direct sequence-code division multiple access radionavigation system
PublicationThis study presents a method of improving time measurements resolution in a direct sequence-code division multiple access receiver by using a fine code tracking loop based on fractional delay filtering of a despreading sequence. It briefly describes the structure of a generic digital code tracking loop and the proposed modification which allows to measure time difference of arrival values with the subsample resolution, together...
-
Modeling DAC Application Execution Time
PublicationAn application written in the Divide And Conquer paradigm is more difficult to model than SPMD application because of complex algorithm, causing use of many coefficients in a computational complexity function. Processors are divided into various layers, each layer contains different number of processors. Data packets processed in different layers and transferred between layers have different length. Moreover first layer processors use...
-
Approximate and analytic flow models for leak detection and identification
PublicationThe article presents a comprehensive quantitative comparison of four analytical models that, in different ways, describe the flow process in transmission pipelines necessary in the task of detecting and isolating leaks. First, the analyzed models are briefly presented. Then, a novel model comparison framework was introduced along with a methodology for generating data and assessing diagnostic effectiveness. The study presents basic...
-
FPGA-Based Implementation of Real Time Optical Flow Algorithm and Its Applications for Digital Image Stabilization
PublicationAn efficient simplification procedure of the optical flow (OF) algorithm as well as its hardware implementation using the field programmable gate array (FPGA) technology is presented. The modified algorithm is based on block matching of subsets of successive frames, and exploits one-dimensional representation of subsets as well as the adaptive adjustments of their sizes. Also, an l1-norm-based correlation function requiring no...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublicationW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Regularized Local Basis Function Approach to Identification of Nonstationary Processes
PublicationThe problem of identification of nonstationary stochastic processes (systems or signals) is considered and a new class of identification algorithms, combining the basis functions approach with local estimation technique, is described. Unlike the classical basis function estimation schemes, the proposed regularized local basis function estimators are not used to obtain interval approximations of the parameter trajectory, but provide...
-
Limitation of Floating-Point Precision for Resource Constrained Neural Network Training
PublicationInsufficient availability of computational power and runtime memory is a major concern when it comes to experiments in the field of artificial intelligence. One of the promising solutions for this problem is an optimization of internal neural network’s calculations and its parameters’ representation. This work focuses on the mentioned issue by the application of neural network training with limited precision. Based on this research,...
-
Novel structure and design of enhanced-bandwidth hybrid quadrature patch coupler
PublicationA novel structure and design optimization procedure of an enhanced-bandwidth hybrid quadrature patch coupler is proposed. Improved performance of the circuit has been obtained by parameterizing the coupler sections using splines, which introduces additional degrees of freedom. Due to computational complexity of the parameter adjustment problem, a sequential design procedure is applied. In each iteration, a selected number of spline...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublicationLet G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
A simplified channel estimation procedure for NB-IoT downlink
PublicationThis paper presents a low-complexity channel estimation procedure which is suitable for use in energy-efficient NB-IoT user equipment devices. The procedure is based on the well-established least squares scheme, followed by linear interpolation in the time domain and averaging in the frequency domain. The quality of channel estimation vs. signal-to-noise ratio is evaluated for two channel models and compared with the performance...