检索结果-内蒙古大学图书馆

randomized naming using wait-free shared variables

DISTRIBUTED COMPUTING 1998年第3期11卷 113-124页

作者： Panconesi, A Papatriantafilou, M Tsigas, P Vitanyi, P Aarhus Univ Dept Comp Sci BRICS DK-8000 Aarhus C Denmark Chalmers Univ Technol Dept Comp Sci S-41296 Gothenburg Sweden CWI NL-1098 SJ Amsterdam Netherlands

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For n processes and is an element of > 0, the protocol uses a name space of size (1 + is an element of)n and O(n log n log log n) running time (read/writes to shared bits) with probability at least 1-o(1), and O(n log(2) n) overall expected running time. The protocol is based on the wait-free implementation of a novel alpha-Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least alpha in the face of the strongest possible adaptive adversary.

关键词： naming problem symmetry breaking unique process ID asynchronous distributed protocols fault-tolerance shared memory wait-free read/write registers atomicity test-and-set objects randomized algorithms adaptive adversary

来源：评论

学校读者我要写书评

暂无评论

randomized time- and energy-optimal routing in single-hop, single-channel radio networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2003年第5期E86A卷 1103-1112页

作者： Bordim, JL Cui, JT Nakano, K Japan Adv Inst Technol Sch Informat Sci Tatsunokuchi Ishikawa 9231292 Japan Nagoya Inst Technol Dept Intelligence & Comp Engn Nagoya Aichi 4668555 Japan

A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RNs, where each station S(i), (1 less than or equal to i less than or equal to p), initially stores si items which are tagged with the unique destination they must be routed. Since each item must be transmitted at least once, every routing protocol must take at least n = s(1) + s(2) + (. . .) + Sp time slots to route each item to its final destination. Similarly, each station S(i), (1 : i P), must be awake for at least si + d(i) time slots to broadcast si items and to receive di items, where di denotes the number of items destined for S(i). The main contribution of this work is to present a randomized time- and energy-optimal routing protocol on the RN. Let q(i), (1 less than or equal to i less than or equal to p), be the number of stations that have items destined for S(i), q = q(1) + q(2) + (. . .) + q(p), and r(i) be the number of stations for which S(i) has items. When qi is known to station S(i), our routing protocol runs, with probability exceeding 1 - 1/f, (f > 1), in n + O(q + log f) time slots with each f station S(i) being awake for at most si + di + O(qi + ri + log f) time slots. Since qi : di, ri : si, and q ! n always hold, our randomized routing protocol is optimal. We also show that, when the value of di is known to S(i), our routing protocol runs, with probability exceeding I - -1, (f > 1), in 0 (n + log f) time slots f with no station being awake for more than O(s(i) + d(i) + log f) time slots.

关键词： radio networks routing protocols energy-efficient randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

FAST randomized NON-HERMITIAN EIGENSOLVERS BASED ON RATIONAL FILTERING AND MATRIX PARTITIONING

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第5期43卷 S791-S815页

作者： Kalantzis, Vassilis Xi, Yuanzhe Horesh, Lior IBM Res Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Emory Univ Dept Math Atlanta GA 30322 USA

This paper describes a set of rational filtering algorithms to compute a few eigenvalues (and associated eigenvectors) of non-Hermitian matrix pencils. Our interest lies in computing eigenvalues located inside a given disk, and the proposed algorithms approximate these eigenvalues and associated eigenvectors by harmonic Rayleigh--Ritz projections on subspaces built by computing range spaces of rational matrix functions through randomized range finders. These rational matrix functions are designed so that directions associated with nonsought eigenvalues are dampened to (approximately) zero. Variants based on matrix partitionings are introduced to further reduce the overall complexity of the proposed framework. Compared with existing eigenvalue solvers based on rational matrix functions, the proposed technique requires no estimation of the number of eigenvalues located inside the disk. Several theoretical and practical issues are discussed, and the competitiveness of the proposed framework is demonstrated via numerical experiments.

关键词： rational filtering matrix partitioning contour integral eigensolvers non-Hermitian eigenvalue problems randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Least Squares Approximation via Sparse Subsampled randomized Hadamard Transform

引用

IEEE TRANSACTIONS ON BIG DATA 2022年第2期8卷 446-457页

作者： Teng, Dan Zhang, Xiaowei Cheng, Li Chu, Delin Natl Univ Singapore Dept Math Block S1710 Lower Kent Ridge Rd Singapore 119076 Singapore ASTAR Bioinformat Inst Singapore 138632 Singapore Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G1H9 Canada

Solving least squares (LS) problems is a major topic in many applications. With recent data explosion, traditional approach is no longer suitable while working with large datasets, instead, randomized algorithms become popular in addressing this issue. In this article we propose a new randomized algorithm - sparse subsampled randomized Hadamard transform (SpSRHT) for solving overdetermined least squares problems. Its unique block structure connects two most commonly used randomized algorithms subsampled randomized Hadamard transform (SRHT) and sparse subspace embedding (SpEmb) and creates a general framework which contains them as special cases. We have shown theoretically that SpSRHT with different parameters reaches the relative-error bound with sketch size ranging from the sketch size required by SpEmb to SRHT. The new algorithm closes the gap between SRHT and SpEmb which provides the possibility of balancing accuracy and efficiency demonstrated in them. This advantage of SpSRHT is also well illustrated in our numerical experiments.

关键词： Transforms Iterative methods Big Data Probability distribution Guidelines Least squares approximations Explosions Least squares randomized algorithms subsampled randomized Hadamard transform sparse subspace embedding

来源：评论

学校读者我要写书评

暂无评论

randomized pursuit-evasion in a polygonal environment

引用

IEEE TRANSACTIONS ON ROBOTICS 2005年第5期21卷 875-884页

作者： Isler, V Kannan, S Khanna, S Univ Calif Berkeley CITRIS Berkeley CA 94720 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply connected polygonal environment, using a randomized strategy. The evader can be arbitrarily faster than the pursuer, and it may know the position of the pursuer at all times, but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm, together with the solution to a problem called the "lion and man problem" as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply connected polygonal environment We show how this strategy can be extended to obtain a strategy for a polygonal room with a door, two pursuers who have only line-of-sight communication, and a single pursuer (at the expense of increased capture time).

关键词： dynamic noncooperative game theory path planning pursuit-evasion games randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A randomized Algorithm for the Exact Solution of Transductive Support Vector Machines

引用

APPLIED ARTIFICIAL INTELLIGENCE 2015年第5期29卷 459-479页

作者： Esposito, G. Martin, M. Univ Politecn Cataluna Dept Comp Sci ES-08034 Barcelona Spain

Random sampling is an efficient method for dealing with constrained optimization problems. In computational geometry, this method has been successfully applied, through Clarkson's algorithm (Clarkson1996), to solve a general class of problems called violator spaces. In machine learning, Transductive Support Vector Machines (TSVM) is a learning method used when only a small fraction of labeled data is available, which implies solving a nonconvex optimization problem. Several approximation methods have been proposed to solve it, but they usually find suboptimal solutions. However, a global optimal solution may be obtained by using exact techniques, but at the cost of suffering an exponential time complexity with respect to the number of instances. In this article, an interpretation of TSVM in terms of violator space is given. A randomized method is presented that extends the use of exact methods, thus reducing the time complexity exponentially w.r.t. the number of support vectors of the optimal solution instead of exponentially w.r.t. the number of instances.

关键词： Constrained optimization complexity classes randomized algorithms Learning methods EXACT SOLUTIONS Approximation method Random sampling Support Vector Network Exact

来源：评论

学校读者我要写书评

暂无评论

Matrix probing: A randomized preconditioner for the wave-equation Hessian

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2012年第2期32卷 155-168页

作者： Demanet, Laurent Letourneau, Pierre-David Boumal, Nicolas Calandra, Henri Chiu, Jiawei Snelson, Stanley MIT Dept Math Cambridge MA 02139 USA Inst Computat Math & Engn Stanford CA USA Catholic Univ Louvain Dept Appl Math Louvain Belgium NYU Courant Inst Math Sci New York NY 10003 USA

This paper considers the problem of approximating the inverse of the wave-equation Hessian, also called normal operator, in seismology and other types of wave-based imaging. An expansion scheme for the pseudodifferential symbol of the inverse Hessian is set up. The coefficients in this expansion are found via least-squares fitting from a certain number of applications of the normal operator on adequate randomized trial functions built in curvelet space. It is found that the number of parameters that can be fitted increases with the amount of information present in the trial functions, with high probability. Once an approximate inverse Hessian is available, application to an image of the model can be done in very low complexity. Numerical experiments show that randomized operator fitting offers a compelling preconditioner for the linearized seismic inversion problem. (C) 2011 Elsevier Inc. All rights reserved.

关键词： randomized algorithms Discrete symbol calculus Curvelets Seismic imaging

来源：评论

学校读者我要写书评

暂无评论

randomized Mixed-Radix Scalar Multiplication

引用

IEEE TRANSACTIONS ON COMPUTERS 2018年第3期67卷 418-431页

作者： Guerrini, Eleonora Imbert, Laurent Winterhalter, Theo Univ Montpellier CNRS LIRMM F-34090 Montpellier France Univ Paris Saclay ENS Cachan F-91190 St Aubin France

A set of congruence relations is a Z-covering if each integer belongs to at least one congruence class from that set. In this paper, we first show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact n-covers, we present a novel uniformly randomized scalar multiplication algorithm with built-in protections against most passive side-channel attacks. Our algorithm randomizes the addition chain using a mixed-radix representation of the scalar. Its reduced overhead and purposeful robustness could make it a sound replacement to several conventional countermeasures. In particular, it is significantly faster than Coron's scalar blinding technique for elliptic curves when the choice of a particular finite field tailored for speed compels to double the size of the scalar, hence the cost of the scalar multiplication.

关键词： Scalar multiplication side-channel attacks randomized algorithms covering systems of congruences mixed-radix number system

来源：评论

学校读者我要写书评

暂无评论

randomized Constraints Consensus for Distributed Robust Mixed-Integer Programming

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第1期8卷 295-306页

作者： Chamanbaz, Mohammadreza Notarstefano, Giuseppe Sasso, Francesco Bouffanais, Roland Singapore Univ Technol & Design Engn Prod Dev EPD Singapore 487372 Singapore Univ Bologna Dept Elect Elect & Informat Engn G Marconi I-40126 Bologna Italy Univ Salento Dept Engn I-73100 Lecce Italy

In this article, we consider a network of processors aiming at cooperatively solving mixed-integer convex programs subject to uncertainty. Each node only knows a common cost function and its local uncertain constraint set. We propose a randomized, distributed algorithm working under asynchronous, unreliable, and directed communication. The algorithm is based on a local computation and communication paradigm. At each communication round, nodes perform two updates: 1) A verification in which they check-in a randomized fashion-the robust feasibility of a candidate optimal point, and 2) an optimization step in which they exchange their candidate basis (the minimal set of constraints defining a solution) with neighbors and locally solve an optimization problem. As a main result, we show that processors can stop the algorithm after a finite number of communication rounds (either because verification has been successful for a sufficient number of rounds or because a given threshold has been reached) so that candidate optimal solutions are consensual. The common solution has proven to be-with high confidence-feasible and, hence, optimal for the entire set of uncertainty except a subset having an arbitrarily small probability measure. We show the effectiveness of the proposed distributed algorithm using two examples: a random, uncertain mixed-integer linear program and a distributed localization in wireless sensor networks. The distributed algorithm is implemented on a multicore platform in which the nodes communicate asynchronously.

关键词： Distributed optimization mixed-integer programming randomized algorithms robust optimization

来源：评论

学校读者我要写书评

暂无评论

randomized DISCRETE EMPIRICAL INTERPOLATION METHOD FOR NONLINEAR MODEL REDUCTION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2020年第3期42卷 A1582-A1608页

作者： Saibaba, Arvind K. North Carolina State Univ Dept Math Raleigh NC 27695 USA

The discrete empirical interpolation method (DEIM) is a popular technique for nonlinear model reduction, and it has two main ingredients: an interpolating basis that is computed from a collection of snapshots of the solution, and a set of indices which determine the nonlinear components to be simulated. The computation of these two ingredients dominates the overall cost of the DEIM algorithm. To specifically address these two issues, we present randomized versions of the DEIM algorithm. There are three main contributions of this paper. First, we use randomized range finding algorithms to efficiently find an approximate DEIM basis. Second, we develop randomized subset selection tools, based on leverage scores, to efficiently select the nonlinear components. Third, we develop several theoretical results that quantify the accuracy of the randomization on the DEIM approximation. We also present numerical experiments that demonstrate the benefits of the proposed algorithms.

关键词： model reduction randomized algorithms discrete empirical interpolation method subset selection subspace iteration

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：