Linear-time Algorithms for Largest Inscribed Quadrilateral
Keikha, Vahideh
2020 - English
Let P be a convex polygon of n vertices. We present a linear-time algorithm for the problem of computing the largest-area inscribed quadrilateral of P. We also design the parallel version of the algorithm with O(log n) time and O(n) work in CREW PRAM model, which is quite work optimal. Our parallel algorithm also computes all the antipodal pairs of a convex polygon with O(log n) time and O(log2n+s) work, where s is the number of antipodal pairs, that we hope is of independent interest. We also discuss several approximation algorithms (both constant factor and approximation scheme) for computing the largest-inscribed k-gons for constant values of k, in both area and perimeter measures.
Keywords:
Maximum-area quadrilateral; extreme area k-gon
Available in a digital repository NRGL
Linear-time Algorithms for Largest Inscribed Quadrilateral
Let P be a convex polygon of n vertices. We present a linear-time algorithm for the problem of computing the largest-area inscribed quadrilateral of P. We also design the parallel version of the ...
Potential Radioactive Hot Spots Induced by Radiation Accident Being Underway of Atypical Low Wind Meteorological Episodes
Pecha, Petr; Tichý, Ondřej; Pechová, E.
2020 - English
Hypothetical radioactivity release with potentially high variability of the source strength is examined. The interactions of the radioactive cloud with surface and atmospheric precipitation are studied and possible adverse consequences on the environment are estimated. The worst-case scenario is devised in two stages starting with a calm meteorological situation succeeded by wind. At the first stage, the discharges of radionuclides into the motionless ambient atmosphere are assumed. During several hours of this calm meteorological situation, a relatively significant level of radioactivity can be accumulated around the source. At the second stage, the calm is assumed to terminate and convective movement of the air immediately starts. The pack of accumulated radioactivity in the form of multiple Gaussian puffs is drifted by wind and pollution is disseminated over the terrain. The results demonstrate the significant transport of radioactivity even behind the protective zone of a nuclear facility (up to between 15 and 20 km). In the case of rain, the aerosols are heavily washed out and dangerous hot spots of the deposited radioactivity can surprisingly emerge even far from the original source of the pollution.
Keywords:
radioactivity; atmospheric dissemination; deposition hot-spots
Fulltext is available at external website.
Potential Radioactive Hot Spots Induced by Radiation Accident Being Underway of Atypical Low Wind Meteorological Episodes
Hypothetical radioactivity release with potentially high variability of the source strength is examined. The interactions of the radioactive cloud with surface and atmospheric precipitation are ...
DEnFi: Deep Ensemble Filter for Active Learning
Ulrych, Lukáš; Šmídl, Václav
2020 - English
Deep Ensembles proved to be a one of the most accurate representation of uncertainty for deep neural networks. Their accuracy is beneficial in the task of active learning where unknown samples are selected for labeling based on the uncertainty of their prediction. Underestimation of the predictive uncertainty leads to poor exploration of the method. The main issue of deep ensembles is their computational cost since multiple complex networks have to be computed in parallel. In this paper, we propose to address this issue by taking advantage of the recursive nature of active learning. Specifically, we propose several methods how to generate initial values of an ensemble based of the previous ensemble. We provide comparison of the proposed strategies with existing methods on benchmark problems from Bayesian optimization and active classification. Practical benefits of the approach is demonstrated on example of learning ID of an IoT device from structured data using deep-set based networks.
Keywords:
Deep Ensembles; uncertainty; neural networks
Fulltext is available at external website.
DEnFi: Deep Ensemble Filter for Active Learning
Deep Ensembles proved to be a one of the most accurate representation of uncertainty for deep neural networks. Their accuracy is beneficial in the task of active learning where unknown samples are ...
Macroeconomic Responses of Emerging Market Economies to Oil Price Shocks: Analysis by Region and Resource Profile
Togonidze, S.; Kočenda, Evžen
2020 - English
This study employs a vector autoregressive (VAR) model to analyse how oil price shocks affect macroeconomic fundamentals in emerging economies. Findings from existing literature remain inconclusive how macroeconomic variables fare towards shocks, especially in emerging economies. The objective of our study is to uncover if analysis by region (Latin America and the Caribbean, East Asia and the Pacific, Europe, and Central Asia) and resource intensity of economies (oil exporters, oil importers, minerals exporters, and less resource intensive). Our unique approach forms part of our contribution to the literature. We find that Latin America and the Caribbean are least affected by oil price shocks, while in East Asia and the Pacific the response of inflation and interest rate to oil price shocks is positive, and output growth is negative. Our analysis by resource endowment fails to show oil price shocks’ ability to explain huge variations in macroeconomic variables in oil importing economies. Further sensitivity analysis using US interest rates as an alternative source of external shocks to emerging economies establishes a significant response of interest rate responses to US interest rate in Europe and Central Asia, and in inflation in Latin America and the Caribbean. We also find that regardless of resource endowment, the response of output growth and capital to a positive US interest rate shock is negative and significant in EMs. Our results are persuasive that resource intensity and regional factors impact the responsiveness of emerging economies to oil price shocks, thus laying a basis for policy debate.\n
Keywords:
Emerging market economies; Oil price shocks; Output growth; Panel VAR
Fulltext is available at external website.
Macroeconomic Responses of Emerging Market Economies to Oil Price Shocks: Analysis by Region and Resource Profile
This study employs a vector autoregressive (VAR) model to analyse how oil price shocks affect macroeconomic fundamentals in emerging economies. Findings from existing literature remain inconclusive ...
The Equation |x| - |Ax| = b
Rohn, Jiří
2020 - English
We formulate conditions on A and b under which the double absolute value equation |x| - |Ax| = b possesses in each orthant a unique solution which, moreover, belongs to the interior of that orthant.
Keywords:
absolute value equation; double absolute value equation; orthantwise solvability; theorem of the alternatives
Available in a digital repository NRGL
The Equation |x| - |Ax| = b
We formulate conditions on A and b under which the double absolute value equation |x| - |Ax| = b possesses in each orthant a unique solution which, moreover, belongs to the interior of that orthant.
A Logical Characteristic of Read-Once Branching Programs
Žák, Stanislav
2019 - English
We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The ”knowledge” arising at a stage of computation in question is derivable from the ”knowledge” arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a ”mystery” information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.‘s but on the other hand in b. p.‘s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems S = (U,D) where U is a universe of knowledge and D are derivation rules. We say that a b.p. P is compatible with a system S iff along each computation in P S derives F (false) or T (true) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm which takes the computational complexity with respect to different classes of restricted b.p.‘s (e.g. read-once b.p.‘s, k-b.p.‘s, b.p.‘s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further we understand the sets U of knowledge(s) as a sets of admissible logical formulae. It is clear that more rich sets U‘s imply the large restrictions on b.p.‘s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness. Another question arises: given a set of Boolean functions (e.g. codes of some graphs) what logical equipment is optimal from the point of complexity?
Keywords:
branching programs; computational complexity; logic
Available in digital repository of the ASCR
A Logical Characteristic of Read-Once Branching Programs
We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two ...
Approximate Bayesian state estimation and output prediction using state-space model with uniform noise
Lainová, Eva; Kuklišová Pavelková, Lenka; Jirsa, Ladislav
2019 - English
This paper contributes to the problem of approximate Bayesian state estimation and output prediction using state space model with uniformly distributed noise. Algorithms for Bayesian filtering and output prediction for states uniformly distributed on an orthotopic support and Bayesian filtering and output prediction for states uniformly distributed on a parallelotopic support are presented and compared.
Keywords:
Bayesian filtering; state estimation; output prediction; uniform noise; parallelotopic support; orthotopic support
Fulltext is available at external website.
Approximate Bayesian state estimation and output prediction using state-space model with uniform noise
This paper contributes to the problem of approximate Bayesian state estimation and output prediction using state space model with uniformly distributed noise. Algorithms for Bayesian filtering and ...
Absolute Value Mapping
Rohn, Jiří
2019 - English
We prove a necessary and sufficient condition for an absolute value mapping to be bijective. This result simultaneously gives a characterization of unique solvability of an absolute value equation for each right-hand side.
Keywords:
absolute value mapping; bijectivity; interval matrix; regularity; absolute value equation; unique solvability
Available in a digital repository NRGL
Absolute Value Mapping
We prove a necessary and sufficient condition for an absolute value mapping to be bijective. This result simultaneously gives a characterization of unique solvability of an absolute value equation for ...
Overdetermined Absolute Value Equations
Rohn, Jiří
2019 - English
We consider existence, uniqueness and computation of a solution of an absolute value equation in the overdetermined case.
Keywords:
absolute value equations; overdetermined system
Available in a digital repository NRGL
Overdetermined Absolute Value Equations
We consider existence, uniqueness and computation of a solution of an absolute value equation in the overdetermined case.
Generalization of a Theorem on Eigenvalues of Symmetric Matrices
Rohn, Jiří
2019 - English
We prove that the product of a symmetric positive semide nite matrix and a symmetric matrix has all eigenvalues real.
Keywords:
symmetric matrix; positive semide nite matrix; real spectrum
Available in a digital repository NRGL
Generalization of a Theorem on Eigenvalues of Symmetric Matrices
We prove that the product of a symmetric positive semide nite matrix and a symmetric matrix has all eigenvalues real.
NRGL provides central access to information on grey literature produced in the Czech Republic in the fields of science, research and education. You can find more information about grey literature and NRGL at service web
Send your suggestions and comments to nusl@techlib.cz
Provider
Other bases