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

Masking patterns in sequences: A new class of motif discovery with don't cares

THEORETICAL COMPUTER SCIENCE 2009年第43期410卷 4327-4340页

作者： Battaglia, Giovanni Cangelosi, Davide Grossi, Roberto Pisanti, Nadia Univ Pisa Dipartimento Informat I-56127 Pisa Italy

We introduce a new notion of motifs, called masks, that Succinctly represents the repeated patterns for an input sequence T of n symbols drawn from an alphabet Sigma. We show how to build the set of all frequent maximal masks of length L in O(2(L)n) time and space in the worst case, using the Karp-Miller-Rosenberg approach. We analytically show that our algorithm performs better than the method based on constant-time enumerating and checking all the potential (vertical bar Sigma vertical bar + 1)(L) candidate patterns in T, after a polynomial-time preprocessing of T. Our algorithm is also cache-friendly, attaining O(2(L) sort(n)) block transfers, where sort(n) is the cache complexity of sorting n items. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Motif inference Pattern with don't care Partial order set doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

Mining Biological Sequences with Masks

Mining Biological Sequences with Masks

引用

20th International Conference on Database and Expert Systems Applications

作者： Battaglia, Giovanni Grossi, Roberto Marangoni, Roberto Pisanti, Nadia Univ Pisa Dipartimento Informat I-56100 Pisa Italy

ISBN: (纸本)9780769537634

A new notion of motifs, called masks, has been introduced in [1], along with the tool MaskMiner to extract them. Masks can be seen as a succinct representation of the repeated patterns occurring in the given input sequence. In this paper we apply this paradigm to mine the sequences of two Glutamate Receptors of human and mouse genomes, and thus discover some properties concerning frequent masks. These experiments will also highlight some interesting peculiarities of MaskMiner.

关键词： Motif inference pattern with don't care partial order set doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

Vibration of fast trains, palindromic eigenvalue problems and structure-preserving doubling algorithms

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2008年第1期219卷 237-252页

作者： Chu, Eric King-Wah Hwang, Tsung-Min Lin, Wen-Wei Wu, Chin-Tien Monash Univ Sch Math Sci Clayton Vic 3800 Australia Natl Taiwan Normal Univ Dept Math Taipei 11677 Taiwan Natl Tsing Hua Univ Dept Math Hsinchu 300 Taiwan Natl Taiwan Ocean Univ Dept Comp Sci & Engn Chilung 20224 Taiwan

The vibration of fast trains is governed by a quadratic palindromic eigenvalue problem (lambda(2)A(1)(T) + lambda A(0) + A(1))x = 0. where A(0), A1 epsilon C-n (x) (n) and A(0)(T) = A(0). Accurate and efficient solution can only be obtained using algorithms which preserve the structure of the eigenvalue problem. This paper reports on the successful application of the structure-preserving doubling algorithms. (C) 2007 Elsevier B.V. All rights reserved.

关键词： palindromic eigenvalue problem nonlinear matrix equation structure-preserving doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2005年第1-3期396卷 55-80页

作者： Chu, EKW Fan, HY Lin, WW Monash Univ Sch Math Sci Clayton Vic 3800 Australia Yuanpei Inst Sci & Technol Dept Finance Hsinchu 300 Taiwan

Continuous-time algebraic Riccati equations (CAREs) can be transformed, a la Cayley, to discrete-time algebraic Riccati equations (DAREs). The efficient structure-preserving doubling algorithm (SDA) for DAREs, front [E.K.-W. Chu, H.-Y. Fan, W.-W. Lin, A structure preserving doubling algorithm for periodic discrete-time algebraic Riccati equations, preprint 2002-28, NCTS, National Tsing Hua University, Hsinchu 300, Taiwan, 2003;E.K.-W. Chu, H.-Y. Fan, W.-W. Lin, C.-S. Wang, A Struture-preserving doubling algorithm for periodic discrete-time algebraic Riccati equations, preprint 2002-18, NCTS, National Tsing Hua University, Hsinchu 300, Taiwan, 2003], can then be applied. In this paper, we develop the structure-preserving doubling algorithm from a new point of view and show its quadratic convergence under assumptions which are weaker than stabilizability and detectability, as well as practical issues involved in the application of the SDA to CAREs. A modified version of the SDA, developed for DAREs with a "doubly symmetric" structure, is also presented. Extensive numerical results show that our approach is efficient and competitive. (C) 2004 Elsevier Inc. All rights reserved.

关键词： Cayley transform continuous-time algebraic Riccati equation doubling algorithm matrix sign function structure-preserving

来源：评论

学校读者我要写书评

暂无评论

An interesting property of the doubling algorithm for solving the discrete time Riccati Equation

An interesting property of the Doubling Algorithm for solvin...

引用

12th International Workshop on Systems, Signals and Image Processing

作者： Assimakis, N Roulis, S Lainiotis, D Triandafillidis, M Technol Educ Inst Lamia Dept Elect Lamia 35100 Greece

In this paper it is shown that the doubling algorithm for solving the discrete time Riccati Equation also provides the steady state solution of a related dual Riccati Equation.

ISBN: (纸本)0907776205

In this paper it is shown that the doubling algorithm for solving the discrete time Riccati Equation also provides the steady state solution of a related dual Riccati Equation.

关键词： Riccati Equation doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

DETECTING AND SOLVING HYPERBOLIC QUADRATIC EIGENVALUE PROBLEMS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2008年第4期30卷 1593-1613页

作者： Guo, Chun-Hua Higham, Nicholas J. Tisseur, Francoise Univ Regina Dept Math & Stat Regina SK S4S 0A2 Canada Univ Manchester Sch Math Manchester M13 9PL Lancs England

Hyperbolic quadratic matrix polynomials Q(lambda) =lambda(2)A + lambda B + C are an important class of Hermitian matrix polynomials with real eigenvalues, among which the overdamped quadratics are those with nonpositive eigenvalues. Neither the definition of overdamped nor any of the standard characterizations provides an efficient way to test if a given Q has this property. We show that a quadratically convergent matrix iteration based on cyclic reduction, previously studied by Guo and Lancaster, provides necessary and sufficient conditions for Q to be overdamped. For weakly overdamped Q the iteration is shown to be generically linearly convergent with constant at worst 1/2, which implies that the convergence of the iteration is reasonably fast in almost all cases of practical interest. We show that the matrix iteration can be implemented in such a way that when overdamping is detected a scalar mu < 0 is provided that lies in the gap between the n largest and n smallest eigenvalues of the n x n quadratic eigenvalue problem (QEP) Q(lambda) x = 0. Once such a mu is known, the QEP can be solved by linearizing to a definite pencil that can be reduced, using already available Cholesky factorizations, to a standard Hermitian eigenproblem. By incorporating an initial preprocessing stage that shifts a hyperbolic Q so that it is overdamped, we obtain an efficient algorithm that identifies and solves a hyperbolic or overdamped QEP maintaining symmetry throughout and guaranteeing real computed eigenvalues.

关键词： quadratic eigenvalue problem hyperbolic overdamped weakly overdamped quadratic matrix polynomial quadratic matrix equation solvent cyclic reduction doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

A new class of nonsymmetric algebraic Riccati equations

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2007年第2-3期426卷 636-649页

作者： Guo, Chun-Hua Univ Regina Dept Math & Stat Regina SK S4S 0A2 Canada

Motivated by the study of linear quadratic differential games, we introduce a new class of nonsymmetric algebraic Riccati equations. It is shown that every equation in this class has a unique stabilizing solution, which is the solution required to find the open-loop Nash equilibrium for the differential game. We show that the doubling algorithm can be used to find this solution efficiently. The solution may also be found by the Schur method, and under further assumptions by Newton's method and a basic fixed-point iteration. (C) 2007 Elsevier Inc. All rights reserved.

关键词： nonsymmetric algebraic Riccati equation H-matrix stabilizing solution Nash equilibrium doubling algorithm Newton's method

来源：评论

学校读者我要写书评

暂无评论

Inner-outer factorization and the inversion of locally finite systems of equations

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2000年第1-3期313卷 53-100页

作者： Dewilde, P van der Veen, AJ Delft Univ Technol DIMES NL-2600 GA Delft Netherlands

We consider the problem of computing the inverse of a large class of infinite systems of linear equations, which are described by a finite set of data. The class consists of equations in which the linear operator is represented by a discrete time-varying dynamical system whose local state space is of finite dimension at each time point k, and which reduces to time invariant systems for time points k --> +/-infinity. In this generalization of classical matrix inversion theory, inner-outer factorizations of operators play the role that QR-factorization plays in classical linear algebra. Numerically, they lead to so-called 'square root' implementations, for which am-active algorithms can be derived, which do not require the determination of spurious multiple eigenvalues, as would be the case if the problem was converted to a discrete time Riccati equation by squaring. We give an overview of the theory and the derivation of the main algorithms. The theory contains both the standard LTI case and the case of a finite set of linear equations as special instances, a particularly instance of which is called 'matrices of low Hanker rank', recently sometimes called 'quasi-separable matrices'. However, in the general case considered here, new phenomena occur which are not observed in these classical cases, namely the occurrence of 'defect spaces'. We describe these and give an algorithm to compute them as well. In all cases, the algorithms given are linear in the amount of data. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： inner-outer factorization URV decomposition QR factorization square-root algorithm Riccati equation Lyapunov-Stein equation system inversion time-varying systems quasi-separable matrices doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

Connectionist network for dynamic programming problems

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 1997年第3期144卷 163-168页

作者： Lam, KP Tong, CW Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong Shatin Hong Kong

Dynamic programming is well known as a powerful modelling technique for dealing with the issue of making optimal decisions sequentially. Many practical problems, such as finding shortest paths in route planning, and multi-stage optimal control, can be formulated as special cases of the general sequential decision process. The paper proposes a connectionist network architecture, called the binary-relation inference network, which solves a special class of dynamic programming problems in the continuous time. They include the all-pair solutions for a family of closed semi-ring path problems, such as shortest paths, transitive closure, minimum spanning tree, and minimax path problems. The all-pair inference network specifies a basic and uniform computation of its individual units, which then collectively emerge towards a global optimal solution. The computational order in its discrete-time variants, either as synchronous or asynchronous networks, bears a close resemblance to the Floyd-Warshall algorithm and doubling algorithm. However, the continuous-time inference network offers a significant speed advantage if its non-sequential computation nature can be exploited. Simulation results of using analogue VLSI implementation of the inference network for solving shortest-path problems are promising.

关键词： connectionist network architecture Floyd-Warshall algorithm doubling algorithm closed semi-ring dynamic programming analogue VLSI circuits

来源：评论

学校读者我要写书评

暂无评论

A survey of recursive algorithms for the solution of the discrete time Riccati Equation

引用

NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS 1997年第4期30卷 2409-2420页

作者： Assimakis, ND Lainiotis, DG Katsikas, SK Sanida, FL Technol Educ Inst Lamia Dept Elect Lamia 35100 Greece Intelligent Syst Technol Melbourne Beach FL 32951 USA Univ Aegean Dept Math Samos 83200 Greece Technol Educ Inst Athens Dept Informat Athens 12210 Greece

The Riccati Equation plays a fundamental role in many fields of mathematics, science and engineering. Its solution constitutes an integral prerequisite to the solution of important problems in the above fields. Due to the importance of the Riccati Equation, there exists considerable literature on its algebraic as well ei algorithmic solution. A very large number of those studies are devoted to the continuous time Riccati Equation. In this paper we present a survey of classical as well as more recant recursive algorithms that solve the discrete time Riccati Equation emanating from the Kalman Filter as well as from the Lainiotis Filter equations either wing per step calculations or the doubling principle. It is established that these algorithms converge fast and are numerically stable.

关键词： estimation Kalman filter Lainiotis filter steady state Riccati Equation general chandrasekhar algorithm doubling algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：