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

Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields

JOURNAL OF SYMBOLIC COMPUTATION 2007年第1-2期42卷 159-177页

作者： Genovese, Giulio Dartmouth Coll Dept Math Hanover NH 03755 USA

A new deterministic algorithm for factoring polynomials over finite fields is presented. This algorithm makes use of linear algebra methods and is an improvement of the Berlekamp algorithm, as well as that of Niederreiter, in the case of nontrivial algebraic extensions. The improvement is achieved by a new method of computing a basis of the so-called Berlekamp primitive subalgebra that makes use of an idea related to the field of Grobner bases. Finally, some comparative running times show how this new deterministic algorithm performs better than other probabilistic algorithms in some practical cases. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： deterministic algorithms finite fields polynomial factorization Berlekamp Niederreiter

来源：评论

学校读者我要写书评

暂无评论

Group spike-and-slab lasso generalized linear models for disease prediction and associated genes detection by incorporating pathway information

引用

BIOINFORMATICS 2018年第6期34卷 901-910页

作者： Tang, Zaixiang Shen, Yueping Li, Yan Zhang, Xinyan Wen, Jia Qian, Chen'ao Zhuang, Wenzhuo Shi, Xinghua Yi, Nengjun Soochow Univ Med Coll Sch Publ Hlth Dept Biostat Suzhou 215123 Peoples R China Soochow Univ Med Coll Jiangsu Key Lab Prevent & Translat Med Geriatr Di Suzhou 215123 Peoples R China Soochow Univ Med Coll Ctr Genet Epidemiol & Genom Suzhou 215123 Peoples R China Univ Alabama Birmingham Dept Biostat Birmingham AL 35294 USA Univ North Carolina Charlotte Dept Bioinformat & Genom Charlotte NC 28223 USA Soochow Univ Sch Biol & Basic Med Sci Dept Bioinformat Suzhou 215123 Peoples R China Soochow Univ Sch Biol & Basic Med Sci Dept Cell Biol Suzhou 215123 Peoples R China

Motivation: Large-scale molecular data have been increasingly used as an important resource for prognostic prediction of diseases and detection of associated genes. However, standard approaches for omics data analysis ignore the group structure among genes encoded in functional relationships or pathway information. Results: We propose new Bayesian hierarchical generalized linear models, called group spike-and-slab lasso GLMs, for predicting disease outcomes and detecting associated genes by incorporating large-scale molecular data and group structures. The proposed model employs a mixture double-exponential prior for coefficients that induces self-adaptive shrinkage amount on different coefficients. The group information is incorporated into the model by setting group-specific parameters. We have developed a fast and stable deterministic algorithm to fit the proposed hierarchal GLMs, which can perform variable selection within groups. We assess the performance of the proposed method on several simulated scenarios, by varying the overlap among groups, group size, number of non-null groups, and the correlation within group. Compared with existing methods, the proposed method provides not only more accurate estimates of the parameters but also better prediction. We further demonstrate the application of the proposed procedure on three cancer datasets by utilizing pathway structures of genes. Our results show that the proposed method generates powerful models for predicting disease outcomes and detecting associated genes.

关键词： HIERARCHICAL Bayes model PROGNOSIS deterministic algorithms DATA analysis GENES

来源：评论

学校读者我要写书评

暂无评论

Leader election in ad hoc radio networks: A keen ear helps

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2013年第7期79卷 1164-1180页

作者： Kowalski, Dariusz R. Pelc, Andrzej Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada

We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. A signal from a transmitting node reaches all neighbors but a message is received successfully by a node, if and only if exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, we say that a collision occurred at this node. Collision detection is the ability of nodes to distinguish a collision from silence. We show that collision detection speeds up leader election in arbitrary radio networks. Our main result is a deterministic leader election algorithm working in time O (n) in all n-node networks, if collision detection is available, while it is known that deterministic leader election requires time Omega(n logn), even for complete networks, if there is no collision detection. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Collision detection deterministic algorithms Distributed algorithms Leader election Radio networks

来源：评论

学校读者我要写书评

暂无评论

High-performance binary and non-binary Low-density parity-check codes based on affine permutation matrices

引用

IET COMMUNICATIONS 2015年第17期9卷 2114-2123页

作者： Gholami, Mohammad Alinia, Masoumeh Inst Res Fundamental Sci IPM Sch Math Tehran Iran Shahrekord Univ Dept Math Shahrekord 115 Iran

Low-density parity-check (LDPC) codes from affine permutation matrices, called APM-LDPC codes, are a class of LDPC codes whose parity-check matrices consist of zero matrices or APMs of the same orders. APM-LDPC codes are not quasi-cyclic (QC), in general. In this study, necessary and sufficient conditions are provided for an APM-LDPC code to have cycles of length 2l, l 2, and a deterministic algorithm is given to generate APM-LDPC codes with a given girth. Unlike Type-I conventional QC-LDPC codes, the constructed (J, L) APM-LDPC codes with the J x L all-one base matrix can achieve minimum distance greater than (J + 1)! and girth larger than 12. Moreover, the lengths of the constructed APM-LDPC codes, in some cases, are smaller than the best known lengths reported for QC-LDPC codes with the same base matrices. Another significant advantage of the constructed APM-LDPC codes is that they have remarkably fewer cycle multiplicities compared with QC-LDPC codes with the same base matrices and the same lengths. Simulation results show that the binary and non-binary constructed APM-LDPC codes with lower girth outperform QC-LDPC codes with larger girth.

关键词： binary codes parity check codes matrix algebra deterministic algorithms cyclic codes high-performance binary low density parity check code high-performance nonbinary low density parity check code affine permutation matrix APM-LDPC base code deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

A work-optimal deterministic algorithm for the certified write-all problem with a nontrivial number of asynchronous processors

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 993-1024页

作者： Malewicz, G Univ Alabama Dept Comp Sci Tuscaloosa AL 35487 USA Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA MIT Supercomp Technol Grp Cambridge MA 02139 USA Univ Connecticut Storrs CT 06269 USA

Martel [ C. Martel, A. Park, and R. Subramonian, SIAM J. Comput., 21 ( 1992), pp. 1070 - 1099] posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental load-balancing and synchronization problem called Certified Write-All (CWA). In this problem, introduced in a slightly different form by Kanellakis and Shvartsman in a PODC' 89 paper [ P. C. Kanellakis and A. A. Shvartsman, Distributed Computing, 5 ( 1992), pp. 201 247], p processors must update n memory cells and only then signal the completion of the updates. It is known that solutions to this problem can be used to simulate synchronous parallel programs on asynchronous systems with worst-case guarantees for the overhead of a simulation. Such simulations are interesting because they may increase productivity in parallel computing since synchronous parallel programs are easier to reason about than are asynchronous ones. This paper presents the first solution to the question of Martel, Park, and Subramonian. Specifically, we show a deterministic asynchronous algorithm for the CWA problem. Our algorithm has the work complexity of O( n + p(4) log n). This work complexity is asymptotically optimal for a nontrivial number of processors p <= ( n/ log n)(1/4). In contrast, all known deterministic algorithms require superlinear in n work when p = n(1/r) for any fixed r >= 1. Our algorithm generalizes the collision principle introduced by Buss et al. [ J. Buss, P. C. Kanellakis, P. L. Ragde, and A. A. Shvartsman, J. algorithms, 20 ( 1996), pp. 45 - 86] in 1996, which has not been previously generalized despite various attempts. Each processor maintains a collection of intervals of {1, 2,..., n}. Any processor iteratively selects an interval and works from its tip toward the other tip until it finishes the work or collides with another processor. Collisions are detected effectively using a special Read-Modify-Write operation. In any case, the processor transforms its collection a

关键词： design and analysis of parallel algorithms deterministic algorithms asynchrony certified write-all

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL AMORTIZED DISTRIBUTED CONSENSUS

引用

INFORMATION AND COMPUTATION 1995年第1期120卷 93-100页

作者： BARNOY, A DENG, X GARAY, JA KAMEDA, T SIMON FRASER UNIV SCH COMP SCIBURNABYBC V5A 1S6CANADA

In this paper we study the behavior of deterministic algorithms when consensus is needed repeatedly, say k times. We show that it is possible to achieve consensus with the optimal number of processors (n > 3t), and when k is large enough, with optimal amortized cost in all other measures: the number of communication rounds r*, the maximal message size m*, and the total bit complexity b*. More specifically, we achieve the following amortized bounds for k consensus instances: r* = O(1 + t/k), b* = O(nt + nt(3)/k), and m* = O(1 + t(2)/k). When k greater than or equal to t(2), then r* and m* are O(1) and b*=O(nt), which is optimal. (C) 1995 Academic Press, Inc.

关键词： Byzantine agreement algorithms Communication Research deterministic algorithms BoNT Greater than or equal to algorithms

来源：评论

学校读者我要写书评

暂无评论

CUTTING HYPERPLANE ARRANGEMENTS

引用

DISCRETE & COMPUTATIONAL GEOMETRY 1991年第5期6卷 385-406页

作者： MATOUSEK, J Charles University

We consider a collection H of n hyperplanes in E(d) (where the dimension d is fixed). An epsilon-cutting for H is a collection of (possibly unbounded) d-dimensional simplices with disjoint interiors, which cover all E(d) and such that the interior of any simplex is intersected by at most epsilon-n hyperplanes of H. We give a deterministic algorithm for finding a (1/r)-cutting with O(r(d)) simplices (which is asymptotically optimal). For r less-than-or-equal-to n 1-delta, where delta > 0 is arbitrary but fixed, the running time of this alogorithm is O(n(log n)O(1)r(d-1)). In the plane we achieve a time bound O(nr) for r less-than-or-equal-to n 1-delta, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For an n point set X is-contained-in-or-equal-to E(d) and a parameter r, we can deterministically compute a (1/r)-net of size O(r log r) for the range space (X, {X intersection R;R is a simplex}), in time O(n(log n)O(1)r(d-1) + r(O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find epsilon-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly.

关键词： deterministic algorithms Simplex Hyperplane Arbitrary plane interior Runtime collection lines Cutting Debris Platanus hybrida Cuttings Optimal self-harm

来源：评论

学校读者我要写书评

暂无评论

A Two-Pulse Cellular Stimulation Test Elucidates Variability and Mechanisms in Signaling Pathways

引用

BIOPHYSICAL JOURNAL 2019年第5期116卷 962-973页

作者： Sumit, Madhuresh Jovic, Andreja Neubig, Richard R. Takayama, Shuichi Linderman, Jennifer J. Univ Michigan Biophys Grad Program Ann Arbor MI 48109 USA Mem Sloan Kettering Canc Ctr Program Mol Pharmacol 1275 York Ave New York NY 10021 USA Michigan State Univ Dept Pharmacol & Toxicol E Lansing MI 48824 USA Univ Michigan Dept Biomed Engn Ann Arbor MI 48109 USA Georgia Inst Technol Wallace H Coulter Dept Biomed Engn Atlanta GA 30332 USA Emory Sch Med Atlanta GA 30322 USA Univ Michigan Dept Chem Engn Ann Arbor MI 48109 USA

Mammalian cells respond in a variable manner when provided with physiological pulses of ligand, such as low concentrations of acetylcholine present for just tens of seconds or TNF alpha for just tens of minutes. For a two-pulse stimulation, some cells respond to both pulses, some do not respond, and yet others respond to only one or the other pulse. Are these different response patterns the result of the small number of ligands being able to only stochastically activate the pathway at random times or an output pattern from a deterministic algorithm responding differently to different stimulation intervals? If the response is deterministic in nature, what parameters determine whether a response is generated or skipped? To answer these questions, we developed a two-pulse test that utilizes different rest periods between stimulation pulses. This "rest-period test" revealed that cells skip responses predictably as the rest period is shortened. By combining these experimental results with a mathematical model of the pathway, we further obtained mechanistic insight into potential sources of response variability. Our analysis indicates that in both intracellular calcium and NF kappa B signaling, response variability is consistent with extrinsic noise (cell-to-cell variability in protein levels), a short-term memory of stimulation, and high Hill coefficient processes. Furthermore, these results support recent works that have emphasized the role of deterministic processes for explaining apparently stochastic cellular response variability and indicate that even weak stimulations likely guide mammalian cells to appropriate fates rather than leaving outcomes to chance. We envision that the rest-period test can be applied to other signaling pathways to extract mechanistic insight.

关键词： Response Variability deterministic algorithms Pathway Torpor deterministic Stimuli Signal Pathways Stimulation stimulation tests Mammalian cells

来源：评论

学校读者我要写书评

暂无评论

deterministic ripple-spreading model for complex networks

引用

Physical Review E 2011年第4期83卷 046123-046123页

作者： Xiao-Bing Hu Ming Wang Mark S. Leeson Evor L. Hines Ezequiel Di Paolo State Key Laboratory of Earth Surface Processes and Resource Ecology Beijing Normal University China School of Engineering University of Warwick Coventry United Kingdom Ikerbasque Basque Science Foundation Centre for Research on Life Mind and Society University of the Basque Country San Sebastian Spain The Centre for Computational Neuroscience and Robotics Department of Informatics University of Sussex Brighton United Kingdom

This paper proposes a deterministic complex network model, which is inspired by the natural ripple-spreading phenomenon. The motivations and main advantages of the model are the following: (i) The establishment of many real-world networks is a dynamic process, where it is often observed that the influence of a few local events spreads out through nodes, and then largely determines the final network topology. Obviously, this dynamic process involves many spatial and temporal factors. By simulating the natural ripple-spreading process, this paper reports a very natural way to set up a spatial and temporal model for such complex networks. (ii) Existing relevant network models are all stochastic models, i.e., with a given input, they cannot output a unique topology. Differently, the proposed ripple-spreading model can uniquely determine the final network topology, and at the same time, the stochastic feature of complex networks is captured by randomly initializing ripple-spreading related parameters. (iii) The proposed model can use an easily manageable number of ripple-spreading related parameters to precisely describe a network topology, which is more memory efficient when compared with traditional adjacency matrix or similar memory-expensive data structures. (iv) The ripple-spreading model has a very good potential for both extensions and applications.

关键词： deterministic algorithms deterministic processes STOCHASTIC processes DATA structures (Computer science) INFORMATION networks DATA transmission systems

来源：评论

学校读者我要写书评

暂无评论

A survey on cloud computing scheduling algorithms

引用

MULTIAGENT AND GRID SYSTEMS 2022年第2期18卷 119-148页

作者： Malekimajd, Marzieh Safarpoor-Dehkordi, Ali Iran Univ Sci & Technol Sch Comp Engn Tehran Iran Iran Univ Sci & Technol Tehran Iran

Cloud computing has emerged as one of the hottest topics in technology and has quickly become a widely used information and communication technology model. Performance is a critical component in the cloud environment concerning constraints like economic, time, and hardware issues. Various characteristics and conditions for providing solutions and designing strategies must be dealt with in different situations to perform better. For example, task scheduling and resource allocation are significant challenges in cloud management. Adopting proper techniques in such conditions leads to performance improvement. This paper surveys existing scheduling algorithms concerning the macro design idea. We classify these algorithms into four main categories: deterministic algorithms, metaheuristic algorithms, learning algorithms, and algorithms based on game theory. Each category is discussed by citing appropriate studies, and the MapReduce review is addressed as an example.

关键词： Cloud computing scheduling deterministic algorithms optimization algorithms metaheuristic algorithms learning algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：