Search

In this paper, we establish some necessary and sufficient conditions for the solvability to a system of two-sided Sylvester-like tensor equations over the quaternion algebra. We also construct an expression of the general solution to the system when it is solvable. As an application, we give some solvability conditions and expressions of the η -Hermitian solutions to some systems of two-sided Sylvester-like quaternion tensor equations. We also provide some algorithms and numerical examples to illustrate the main results of this paper. [ABSTRACT FROM AUTHOR]

In this paper, we propose an algorithm for solving the Cauchy problem for a two-dimensional difference equation with constant coefficients at a point, based on its coefficients and the initial data for the Cauchy problem, which are defined in a "strip." For this purpose, computer algebra methods are employed. To automate the process of computing the solution, the algorithm is implemented in MATLAB, with the input data being the matrix of coefficients of the two-dimensional polynomial difference equation, the coordinates of the initial data matrix (which defines the structure of the difference equation), and the coordinates of the point that determines the dimension of the initial data matrix. The output of the algorithm is a solution of the Cauchy problem (with the initial data defined in a "strip") for the two-dimensional difference equation, which is a function value at the desired point. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new class of algebras satisfying certain conditions which has been named power algebras and we prove some fixed point theorems for a new class of contractions. We give new conditions for the existence and uniqueness of fixed points for this new class of mappings which are not a contraction in the usual algebra. Also, we introduce a new iterative algorithm for fixed-point problems in a Banach algebra. This results improve and extend the corresponding conclusions of the Ishikawa algorithm under weaker conditions and lead to stronger results. In conclusion, we give an application to nonlinear integral equations. [ABSTRACT FROM AUTHOR]

The article announces the selection of the study "Decomposition Algorithms for Stochastic Programming on a Computational Grid," written by Jeff Linderoth and Stephen Wright by the editorial board of the periodical "Computational Optimization and Applications," for the Best Paper Award 2004. The paper describes research carried out by the authors at the Argonne National Laboratory which was supported by the National Science Foundation (NSF). The research involved the development of middleware software, the discovery of new algorithms that could exploit the power of grid platforms while not being affected too seriously by its less felicitous features and the implementation of these algorithms using the resulting codes to solve touchstone problems in optimization.

Based on the Bochner–Martinelli integral representation, an algorithm for determining the number of zeros of a system of holomorphic functions is developed. We search for zeros of the system in a polycube. The use of computer algebra methods in this problem is due to the computational complexity of the developed algorithms and final results. The algorithm is implemented in Maple, which makes it possible to significantly facilitate the necessary computations. [ABSTRACT FROM AUTHOR]

Motivated by several applications, we investigate the well-posedness of a switched system composed by a system of linear hyperbolic balance laws and by a system of linear algebraic differential equations. This setting includes networks and looped systems of hyperbolic balance laws. The obtained results are globally in time, provided that the inputs have finite (but not necessarily small) total variation. [ABSTRACT FROM AUTHOR]

Abstract Current implicit blending techniques are mostly designed for use in surface modelling, where only boundaries of the object defined by the implicit primitives are important. In contrast, in volumetric implicit modelling the interior of the object is also significant, which requires different and more suitable techniques for combining implicit primitives. In this paper, we first discuss irregularities that occur using the current techniques. Then, a new technique for blending implicit primitives, especially appropriate in volumetric modelling (e.g., cloud modelling), is introduced. It overcomes these abnormalities and gives us better results than current techniques. [ABSTRACT FROM AUTHOR]

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

Anzai skew-products are shown to be uniquely ergodic with respect to the fixed-point subalgebra if and only if there is a unique conditional expectation onto such a subalgebra which is invariant under the dynamics. For the particular case of skew-products, this solves a question raised by B. Abadie and K. Dykema in the wider context of C ∗ -dynamical systems. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding the generators of the solution space for a system of inequalities A ⊗ x ≥ x in max-plus algebra. It provides an improved algorithm which can be used to find a smaller set of generators for the solution space by skipping a large number of invalid generators. [ABSTRACT FROM AUTHOR]

The chosen-message method is used to be employed in conducting Simple Power Analysis (SPA) attack by means of selecting special input messages. However, it is difficult to make distinction by visual observation i.e., SPA in practical IoT hardware environment. In this paper, we proposed a practical chosen-message correlation power analysis (CPA) attack which combines the chosen-message method with CPA for side channel attack. Then, we adopt other two practical chosen-messages, 1 and n + 1, to attack Boscher's right-to-left binary exponentiation algorithm which is wildly considered as an efficient side channel resistant algorithm. Finally, this paper presents a countermeasure to resist the chosen-message CPA attack over Boscher's algorithm without nullifying its countermeasure features to Differential Power Analysis (DPA) and Differential Fault Analysis (DFA). To validate the proposed attack method and countermeasure, a 1024-bit RSA coprocessor is constructed on the Xilinx Virtex-5 with the Side-channel Attack Standard Evaluation Board (SASEBO) to implement Boscher's algorithm as well as our proposed algorithm and launched the proposed attack on it separately. The experiment results show that the proposed attack and countermeasure are feasible and efficient. [ABSTRACT FROM AUTHOR]

In a paper published in 2013, Wang and Ma proposed a structure-preserving algorithm for computing the quaternion LU decomposition. They claimed that it was faster than the LU decomposition implemented in the quaternion Toolbox for Matlab (QTFM). But in 2015, Sangwine, one of the authors of QTFM, pointed out that the tests carried out by him did not support Wang and Ma's claim. We studied the structure-preserving algorithm of Wang and Ma, and found that the computations were based on element to element operations. In this paper, we re-propose real structure-preserving methods for the quaternion LU decomposition and partial pivoting quaternion LU decomposition, which make full use of high-level operations, and relation of operations between quaternion matrices and their real representation matrices. These algorithms are more efficient than that in QTFM using quaternion arithmetics. Numerical experiments are provided to demonstrate the efficiency of the real structure-preserving method. [ABSTRACT FROM AUTHOR]

In recent years, cases of newly emergent induced clusters have increased seismic hazard and risk in locations with social, environmental, and economic consequence. Thus, the need for a quantitative and robust means to discern induced seismicity has become a critical concern. This paper reviews a Matlab-based algorithm designed to quantify the statistical confidence between two time-series datasets. Similar to prior approaches, our method utilizes the cross-correlation to delineate the strength and lag of correlated signals. In addition, use of surrogate reshuffling tests allows for the dynamic testing against statistical confidence intervals of anticipated spurious correlations. We demonstrate the robust nature of our algorithm in a suite of synthetic tests to determine the limits of accurate signal detection in the presence of noise and sub-sampling. Overall, this routine has considerable merit in terms of delineating the strength of correlated signals, one of which includes the discernment of induced seismicity from natural. [ABSTRACT FROM AUTHOR]

Multipath interference seriously degrades the performance of Global Navigation Satellite System (GNSS) positioning in an urban canyon. Most current multipath mitigation algorithms suffer from heavy computational load or need external assistance. We propose a multipath mitigation algorithm based on the steepest descent approach, which has the merits of less computational load and no need for external aid. A new ranging code tracking loop is designed based on the steepest descent method, which can save an early branch or a late branch compared with the narrow-spacing correlation method. The power of the Non-Line-of-Sight (NLOS) signal is weaker than that of the Line-of-Sight (LOS) signal when the LOS signal is not obstructed and with a relatively high Carrier Noise Ratio (CNR). The peak position in the X-axis of the ranging code autocorrelation function does not move with the NLOS interference. Meanwhile, the cost function is designed according to this phenomenon. The results demonstrate that the proposed algorithm outperforms the narrow-spacing correlation and the Multipath Estimated Delay Locked Loop (MEDLL) in terms of the code multipath mitigation and computation time. The Standard Deviation (STD) of the tracking error with the proposed algorithm is less than 0.016 chips. Moreover, the computation time of the proposed algorithm in a software defined receiver is shortened by 24.21% compared with the narrow-spacing correlation. [ABSTRACT FROM AUTHOR]

We consider the Geometria Practica of Christopher Clavius, S.J., a surprisingly eclectic and comprehensive practical geometry text, whose first edition appeared in 1604. Our focus is on four particular sections from Books IV and VI where Clavius has either used his sources in an interesting way or where he has been uncharacteristically reticent about them. These include the treatments of Heron's Formula, Archimedes' Measurement of the Circle, four methods for constructing two mean proportionals between two lines, and finally an algorithm for computing nth roots of numbers. [ABSTRACT FROM AUTHOR]

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS-ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS-ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Polycube construction and deformation are essential problems in computer graphics. In this paper, we present a robust, simple, efficient, and automatic algorithm to deform the meshes of arbitrary shapes into polycube form. We derive a clear relationship between a mesh and its corresponding polycube shape. Our algorithm is edge-preserving, and works on surface meshes with or without boundaries. Our algorithm outperforms previous ones with respect to speed, robustness, and efficiency. Our method is simple to implement. To demonstrate the robustness and effectivity of our method, we have applied it to hundreds of models of varying complexity and topology. We demonstrate that our method compares favorably to other state-of-the-art polycube deformation methods. [ABSTRACT FROM AUTHOR]

With the development of science and technology, the popularity of smart phones has made exponential growth in mobile phone application market. How to help users to select applications they prefer has become a hot topic in recommendation algorithm. As traditional recommendation algorithms are based on popularity and download, they inadvertently fail to recommend the desirable applications. At the same time, many users tend to pay more attention to permissions of those applications, because of some privacy and security reasons. There are few recommendation algorithms which take account of apps' permissions, functionalities and users' interests altogether. Some of them only consider permissions while neglecting the users' interests, others just perform linear combination of apps' permissions, functionalities and users' interests to implement top-N recommendation. In this paper, we devise a recommendation method based on both permissions and functionalities. After demonstrating the correlation of apps' permissions and users' interests, we design an app risk score calculating method ARSM based on app-permission bipartite graph model. Furthermore, we propose a novel matrix factorization algorithm MFPF based on users' interests, apps' permissions and functionalities to handle personalized app recommendation. We compare our work with some of the state-of-the-art recommendation algorithms, and the results indicate that our work can improve the recommendation accuracy remarkably. [ABSTRACT FROM AUTHOR]

The paper establishes the invariance of the simplex-module algorithm for expanding real numbers α = (α1, …, αd) in multidimensional continued fractions under linear-fractional transformations α′=α1′…αd1=Uα with matrices U from the unimodular group GLd+1(ℤ). It is shown that the convergents of the transformed collections of numbers α′ satisfy the same recurrence relation and have the same approximation order. [ABSTRACT FROM AUTHOR]

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations. [ABSTRACT FROM AUTHOR]

Providing anonymous communication on networks of interconnected computers is an active area of research which aims to enhance the privacy of the users of such networks. Communication unobservability, stronger property compared to anonymity, attempts to guarantee that legitimate messages are not discernible from dummy traffic. A network with an active global adversary is one which it is assumed that all nodes in the network are potentially being monitored at all times, and also that at any time any node could be an adversary. This paper introduces a set of anonymous system design requirements for providing enhanced communication unobservability. A new anonymous networking system was designed based on these requirements to provide both sender and receiver anonymity. The proposed system has a structured peer-to-peer network architecture and a randomized routing algorithm to obfuscate the detection of communication paths and the message routing patterns. An age-based method is proposed to prevent even the first node after the sender from identifying the original sender. A simulation program was designed and implemented to test the proposed system. The effect of different parameters on the proposed algorithm is demonstrated using a simulation program. [ABSTRACT FROM AUTHOR]

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) we present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication cost of CAS is $$\frac{N}{N-2f}$$ . The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with garbage collection (CASGC). The CASGC algorithm is parameterized by an integer $$\delta $$ and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter $$\delta $$ where the number of server failures is no bigger than f, a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than $$\delta $$ . We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of $$\frac{N}{N-f}$$ measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC. [ABSTRACT FROM AUTHOR]

Due to the time-variant channel, outdated channel state information (CSI) largely reduce the performance of double codebook beamforming system. This paper studies the two codebooks independently and proposes an adaptive feedback period adjustment Strategy for long-term codebook and a prediction estimation algorithm for short-term codebook respectively. The former dynamically adjusts feedback period so as to improve the feedback timeliness and uplink feedback resource utilization. The later adopts improved Kalman prediction algorithm to predict CSI. Finally simulation results shows that the proposed schemes can effectively improve the performance of double codebook estimation with outdated CSI. [ABSTRACT FROM AUTHOR]

Saliency text is that characters are ordered with visibility and expressivity. It also contains important clues for video analysis, indexing, and retrieval. Thus, in order to localize the saliency text, a critical stage is to collect key points from real text pixels. In this paper, we propose an evidence-based model of saliency feature extraction (SFE) to probe saliency text points (STPs), which have strong text signal structure in multi-observations simultaneously and always appear between text and its background. Through the multi-observations, each signal structure with rhythms of signal segments is extracted at every location in the visual field. It supports source of evidences for our evidence-based model, where evidences are measured to effectively estimate the degrees of plausibility for obtaining the STP. The evaluation results on benchmark datasets also demonstrate that our proposed approach achieves the state-of-the-art performance on exploring real text pixels and significantly outperforms the existing algorithms for detecting text candidates. The STPs can be the extremely reliable text candidates for future text detectors. [ABSTRACT FROM AUTHOR]

We prove that if an n-element algebra generates the variety V which is actively structurally complete, then the cardinality of the carrier of each subdirectly irreducible algebra in V is at most n (n + 1) · n 2 · n . As a consequence, with the use of known results, we show that there exist algorithms deciding whether a given finite algebra A generates the (actively) structurally complete variety V (A) in the cases when V (A) is congruence modular or V (A) is congruence meet-semidistributive or A is a semigroup. [ABSTRACT FROM AUTHOR]

The primary goal of the secure socket layer protocol (SSL) is to provide confidentiality and data integrity between two communicating entities. Since the most computationally expensive step in the SSL handshake protocol is the server's RSA decryption, it is introduced that the proposed secret exchange algorithm can be used to speed up the SSL session initialization. This paper first points out that the previous batch method is impractical since it requires multiple certificates. It then proposes a unique certificate scheme to overcome the problem. The optimization strategy, which is based on the constrained model considering the user requirements-aware security ranking, focuses on the optimal result in different public key sizes. It is also introduced that the parameter is optimized when integrating user requirements for Internet QoS, such as the stability of the system and the tolerable response time. Finally, the proposed algorithm is evaluated to be practical and efficient through both analysis and simulation studies. [ABSTRACT FROM AUTHOR]

We present efficient algorithms to compute simple and complex map algebra operations over raster data stored in main memory, using the k2-acc compact data structure. Raster data correspond to numerical data that represent attributes of spatial objects, such as temperature or elevation measures. Compact data structures allow efficient data storage in main memory and query them in their compressed form. A k2-acc is a set of k2-trees, one for every distinct numeric value in the raster matrix. We demonstrate that map algebra operations can be computed efficiently using this compact data structure. In fact, some map algebra operations perform over five orders of magnitude faster compared with algorithms working over uncompressed datasets. [ABSTRACT FROM AUTHOR]

We propose a simple model for distributed query processing based on the concept of a distributed array. Such an array has fields of some data type whose values can be stored on different machines. It offers operations to manipulate all fields in parallel within the distributed algebra. The arrays considered are one-dimensional and just serve to model a partitioned and distributed data set. Distributed arrays rest on a given set of data types and operations called the basic algebra implemented by some piece of software called the basic engine. It provides a complete environment for query processing on a single machine. We assume this environment is extensible by types and operations. Operations on distributed arrays are implemented by one basic engine called the master which controls a set of basic engines called the workers. It maps operations on distributed arrays to the respective operations on their fields executed by workers. The distributed algebra is completely generic: any type or operation added in the extensible basic engine will be immediately available for distributed query processing. To demonstrate the use of the distributed algebra as a language for distributed query processing, we describe a fairly complex algorithm for distributed density-based similarity clustering. The algorithm is a novel contribution by itself. Its complete implementation is shown in terms of the distributed algebra and the basic algebra. As a basic engine the Secondo system is used, a rich environment for extensible query processing, providing useful tools such as main memory M-trees, graphs, or a DBScan implementation. [ABSTRACT FROM AUTHOR]

Problems are often too complex to solve them in an optimal way. The complexity arises from connections between their elements, such that a change in one element influences the performance of other elements. Kauffman’s NK model offers a way to depict such interdependencies and has therefore often been used in economic investigations of the influence of problem or search decomposition on the attainable results. However, papers on the effect of different decompositions on solution quality come to contradictory conclusions. Some observe an initial advantage of over-modularization where others do not. As they also differ in the employed search procedures, but do not base them on empirical findings, the present paper examines the results of more empirically based search strategies. Using algorithms based on innovation strategies derived from patent data, the paper establishes a clear advantage of correct problem decompositions. [ABSTRACT FROM AUTHOR]

This paper starts a series of publications devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices. The paper considers rank factorizations and, in particular, the relatively irreducible and ΔW-2 factorizations, which are used in solving spectral problems for two-parameter polynomial matrices F(λ, µ). Algorithms for computing these factorizations are suggested and applied to computing points of the regular, singular, and regular-singular spectra and the corresponding spectral vectors of F(λ, µ). The computation of spectrum points reduces to solving algebraic equations in one variable. A new method for computing spectral vectors for given spectrum points is suggested. Algorithms for computing critical points and for constructing a relatively free basis of the right null-space of F(λ, µ) are presented. Conditions sufficient for the existence of a free basis are established, and algorithms for checking them are provided. An algorithm for computing the zero-dimensional solutions of a system of nonlinear algebraic equations in two variables is presented. The spectral properties of the ΔW-2 method are studied. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

The multiple-sets split equality problem, a generalization and extension of the split feasibility problem, has a variety of specific applications in real world, such as medical care, image reconstruction, and signal processing. It can be a model for many inverse problems where constraints are imposed on the solutions in the domains of two linear operators as well as in the operators’ ranges simultaneously. Although, for the split equality problem, there exist many algorithms, there are but few algorithms for the multiple-sets split equality problem. Hence, in this paper, we present a relaxed two points projection method to solve the problem; under some suitable conditions, we show the weak convergence and give a remark for the strong convergence method in the Hilbert space. The interest of our algorithm is that we transfer the problem to an optimization problem, then, based on the model, we present a modified gradient projection algorithm by selecting two different initial points in different sets for the problem (we call the algorithm as two points algorithm). During the process of iteration, we employ subgradient projections, not use the orthogonal projection, which makes the method implementable. Numerical experiments manifest the algorithm is efficient. [ABSTRACT FROM AUTHOR]

In this paper, we propose two iterative algorithms for finding the minimum-norm solution of a split minimization problem. We prove strong convergence of the sequences generated by the proposed algorithms. The iterative schemes are proposed in such a way that the selection of the step-sizes does not need any prior information about the operator norm. We further give some examples to numerically verify the efficiency and implementation of our new methods and compare the two algorithms presented. Our results act as supplements to several recent important results in this area. [ABSTRACT FROM AUTHOR]

In the literature, most known sequence transformations can be written as a ratio of two determinants. But, it is not always this case. One exception is that the sequence transformation proposed by Brezinski, Durbin, and Redivo-Zaglia cannot be expressed as a ratio of two determinants. Motivated by this, we will introduce a new algebraic tool—pfaffians, instead of determinants in the paper. It turns out that Brezinski-Durbin-Redivo-Zaglia’s transformation can be expressed as a ratio of two pfaffians. To the best of our knowledge, this is the first time to introduce pfaffians in the expressions of sequence transformations. Furthermore, an extended transformation of high order is presented in terms of pfaffians and a new convergence acceleration algorithm for implementing the transformation is constructed. Then, the Lax pair of the recursive algorithm is obtained which implies that the algorithm is integrable. Numerical examples with applications of the algorithm are also presented. [ABSTRACT FROM AUTHOR]

This paper is concerned with the reformulation of Neumann-Neumann waveform relaxation (NNWR) methods and Dirichlet-Neumann waveform relaxation (DNWR) methods, a family of parallel space-time approaches to solving time-dependent PDEs. By changing the order of the operations, pipeline-parallel computation of the waveform iterates are possible, without changing the solution of each waveform iterate. The parallel efficiency of the pipeline implementation is analyzed, as well as the change in the communication pattern. Numerical studies are presented to show the effectiveness of the pipeline NNWR and DNWR algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider solving a set of global optimization problems in parallel. The proposed novel algorithm provides uniform convergence to the set of solutions for all problems treated simultaneously. The current accuracy for each particular solution is estimated by the difference in each coordinate from the point of global decision. The main statement is given in the corresponding theorem. For the sake of illustration some computational results with hundreds of multidimensional global problems are provided. [ABSTRACT FROM AUTHOR]

We consider a global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Our approach is based on the well-known DIRECT (DIviding RECTangles) algorithm and motivated by the diagonal partitioning strategy. One of the main advantages of the diagonal partitioning scheme is that the objective function is evaluated at two points at each hyper-rectangle and, therefore, more comprehensive information about the objective function is considered than using the central sampling strategy used in most DIRECT-type algorithms. In this paper, we introduce a new DIRECT-type algorithm, which we call BIRECT (BIsecting RECTangles). In this algorithm, a bisection is used instead of a trisection which is typical for diagonal-based and DIRECT-type algorithms. The bisection is preferable to the trisection because of the shapes of hyper-rectangles, but usual evaluation of the objective function at the center or at the endpoints of the diagonal are not favorable for bisection. In the proposed algorithm the objective function is evaluated at two points on the diagonal equidistant between themselves and the endpoints of a diagonal. This sampling strategy enables reuse of the sampling points in descendant hyper-rectangles. The developed algorithm gives very competitive numerical results compared to the DIRECT algorithm and its well know modifications. [ABSTRACT FROM AUTHOR]

When combining very different images which often contain complex objects and backgrounds, producing consistent compositions is a challenging problem requiring seamless image editing. In this paper, we propose a general approach, called object-aware image editing, to obtain consistency in structure, color, and texture in a unified way. Our approach improves upon previous gradient-domain composition in three ways. Firstly, we introduce an iterative optimization algorithm to minimize mismatches on the boundaries when the target region contains multiple objects of interest. Secondly, we propose a mixed-domain consistency metric for measuring gradients and colors, and formulate composition as a unified minimization problem that can be solved with a sparse linear system. In particular, we encode texture consistency using a patch-based approach without searching and matching. Thirdly, we adopt an object-aware approach to separately manipulate the guidance gradient fields for objects of interest and backgrounds of interest, which facilitates a variety of seamless image editing applications. Our unified method outperforms previous state-of-the-art methods in preserving global texture consistency in addition to local structure continuity. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel approach for assessing and interacting with surface tracking algorithms targeting video manipulation in post-production. As tracking inaccuracies are unavoidable, we enable the user to provide small hints to the algorithms instead of correcting erroneous results afterwards. Based on 2D mesh warp-based optical flow estimation, we visualize results and provide tools for user feedback in a consistent reference system, texture space. In this space, accurate tracking results are reflected by static appearance, and errors can easily be spotted as apparent change. A variety of established tools can be utilized to visualize and assess the change between frames. User interaction to improve tracking results becomes more intuitive in texture space, as it can focus on a small region rather than a moving object. We show how established tools can be implemented for interaction in texture space to provide a more intuitive interface allowing more effective and accurate user feedback. [ABSTRACT FROM AUTHOR]

This paper introduces a new algorithm for solving large-scale continuous-time algebraic Riccati equations (CARE). The advantage of the new algorithm is in its immediate and efficient low-rank formulation, which is a generalization of the Cholesky-factored variant of the Lyapunov ADI method. We discuss important implementation aspects of the algorithm, such as reducing the use of complex arithmetic and shift selection strategies. We show that there is a very tight relation between the new algorithm and three other algorithms for CARE previously known in the literature-all of these seemingly different methods in fact produce exactly the same iterates when used with the same parameters: they are algorithmically different descriptions of the same approximation sequence to the Riccati solution. [ABSTRACT FROM AUTHOR]

This paper is concerned with the implementation of efficient solution algorithms for elliptic problems with constraints. We establish theory which shows that including a simple scaling within well-established block diagonal preconditioners for Stokes problems can result in significantly faster convergence when applying the preconditioned MINRES method. The codes used in the numerical studies are available online. [ABSTRACT FROM AUTHOR]

Finding optimal Golomb rulers is an extremely challenging combinatorial problem. The distance between each pair of mark is unique in a Golomb ruler. For a given number of marks, an optimal Golomb ruler has the minimum length. Golomb rulers are used in application areas such as X-ray crystallography, radio astronomy, information theory, and pulse phase modulation. The most recent optimal Golomb ruler search algorithm hybridises a range of techniques such as greedy randomised adaptive search, scatter search, tabu search, clustering techniques, and constraint programming, and obtains optimal Golomb rulers of up to 16 marks with very low success rates. In this paper, we provide tight upper bounds for Golomb ruler marks and present heuristic-based effective domain reduction techniques. Using these along with tabu and configuration checking meta-heuristics, we then develop a constraint-based multi-point local search algorithm to perform a satisfaction search for optimal Golomb rulers of specified length. We then present an algorithm to perform an optimisation search that minimises the length using the satisfaction search repeatedly. Our satisfaction search finds optimal Golomb rulers of up to 19 marks while the optimisation search finds up to 17 marks. [ABSTRACT FROM AUTHOR]

In this paper we analyze the convergence properties of two-level and W-cycle multigrid solvers for the numerical solution of the linear system of equations arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polygonal/polyhedral meshes. We prove that the two-level method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the number of smoothing steps, which depends on p, is chosen sufficiently large. An analogous result is obtained for the W-cycle multigrid algorithm, which is proved to be uniformly convergent with respect to the mesh size, the polynomial approximation degree, and the number of levels, provided the number of smoothing steps is chosen sufficiently large. Numerical experiments are presented which underpin the theoretical predictions; moreover, the proposed multilevel solvers are shown to be convergent in practice, even when some of the theoretical assumptions are not fully satisfied. [ABSTRACT FROM AUTHOR]

In this paper, we derive novel representations of generalized inverses $$A^{(1)}_{T,S}$$ and $$A^{(1,2)}_{T,S}$$ , which are much simpler than those introduced in Ben-Israel and Greville (Generalized inverses: theory and applications. Springer, New York, 2003). When $$A^{(1,2)}_{T,S}$$ is applied to matrices of index one, a simple representation for the group inverse $$A_{g}$$ is derived. Based on these representations, we derive various algorithms for computing $$A^{(1)}_{T,S}$$ , $$A^{(1,2)}_{T,S}$$ and $$A_{g}$$ , respectively. Moreover, our methods can be achieved through Gauss-Jordan elimination and complexity analysis indicates that our method for computing the group inverse $$A_{g}$$ is more efficient than the other existing methods in the literature for a large class of problems in the computational complexity sense. Finally, numerical experiments show that our method for the group inverse $$A_{g}$$ has highest accuracy among all the existing methods in the literature and also has the lowest cost of CPU time when applied to symmetric matrices or matrices with high rank or small size matrices with low rank in practice. [ABSTRACT FROM AUTHOR]

In this paper, the normwise condition number of a linear function of the equality constrained linear least squares solution called the partial condition number is considered. Its expression and closed formulae are first presented when the data space and the solution space are measured by the weighted Frobenius norm and the Euclidean norm, respectively. Then, we investigate the corresponding structured partial condition number when the problem is structured. To estimate these condition numbers with high reliability, the probabilistic spectral norm estimator and the small-sample statistical condition estimation method are applied and two algorithms are devised. The obtained results are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, a novel energy-preserving numerical scheme for nonlinear Hamiltonian wave equations with Neumann boundary conditions is proposed and analyzed based on the blend of spatial discretization by finite element method (FEM) and time discretization by Average Vector Field (AVF) approach. We first use the finite element discretization in space, which leads to a system of Hamiltonian ODEs whose Hamiltonian can be thought of as the semi-discrete energy of the original continuous system. The stability of the semi-discrete finite element scheme is analyzed. We then apply the AVF approach to the Hamiltonian ODEs to yield a new and efficient fully discrete scheme, which can preserve exactly (machine precision) the semi-discrete energy. The blend of FEM and AVF approach derives a new and efficient numerical scheme for nonlinear Hamiltonian wave equations. The numerical results on a single-soliton problem and a sine-Gordon equation are presented to demonstrate the remarkable energy-preserving property of the proposed numerical scheme. [ABSTRACT FROM AUTHOR]

It has been pointed out by Jones D. R. that the DIRECT global optimization algorithm can quickly get close to the basin of the optimum but takes longer to achieve a high degree of accuracy. In this paper, we introduce a bilevel strategy into a modifed DIRECT algorithm to overcome this shortcoming. The proposed algorithm is proved to be convergent globally. Numerical results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

In the paper, the non-separability relation for finite state machines with time-outs is studied. A specific feature of such machines is integer-valued delays, or time-outs, which determine how long the finite state machine will stay in one or another state if there are no input actions. If the time-out is over and no input symbol has been applied, then the TFSM state is changed according to the transition under time delay. In the paper, an algorithm for constructing a separating sequence for such finite state machines is presented. Here, the separating sequence is a timed input sequence for which sets of input sequences of the TFSM do not intersect; hence, it is sufficient to apply the separating sequence once in order to distinguish the TFSMs by their output reactions. This algorithm underlies the algorithm for construction of test suites with respect to non-separability relation in the case where the fault domain is specified by means of a mutation machine. Test suite derivation with respect to non-separability relation by way of 'TFSM to FSM' transformation is discussed. [ABSTRACT FROM AUTHOR]

We show how to use Gromov-Witten invariants to determine the matter content of F-theory compactifications on elliptically fibered Calabi-Yau manifolds X over Hirzebruch surfaces. To determine the representations of these matter multiplets under the gauge algebra g , we use toric methods to embed the weight lattice of g into the integer homology lattice of X. We then apply mirror symmetry to determine whether classes in this lattice which correspond to weights of given representations are represented by irreducible curves. Applying mirror symmetry efficiently to such geometries requires obtaining good approximations to their Mori cones. We propose an algorithm for obtaining such approximations. When the algorithm yields a smooth cone, we find that the latter in fact coincides with the Mori cone of X and already contains information on the matter content of compactifications on X. Our algorithm relies on studying toric ambient spaces for the Calabi-Yau hypersurface X which are merely birationally equivalent to fibrations over Hirzebruch surfaces. We study the flops relating such varieties in detail. [ABSTRACT FROM AUTHOR]

Discovering approximately recurrent motifs (ARMs) in timeseries is an active area of research in data mining. Exact motif discovery is defined as the problem of efficiently finding the most similar pairs of timeseries subsequences and can be used as a basis for discovering ARMs. The most efficient algorithm for solving this problem is the MK algorithm which was designed to find a single pair of timeseries subsequences with maximum similarity at a known length. This paper provides three extensions of the MK algorithm that allow it to find the top K similar subsequences at multiple lengths using both the Euclidean distance metric and scale invariant normalized version of it. The proposed algorithms are then applied to both synthetic data and real-world data with a focus on discovery of ARMs in human motion trajectories. [ABSTRACT FROM AUTHOR]