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

An equation-based algorithmic differentiation technique for differential algebraic equations

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2015年 281卷 135-151页

作者： Elsheikh, Atiyah Austrian Inst Technol Vienna Austria

This work presents a novel Algorithmic Differentiation (AD) approach for sensitivity analysis of Differential Algebraic Equation systems (DAEs). For the first time, the algorithmic specification of a computationally memory-efficient equation-based AD technique is presented. This approach is mainly targeting equation-based modeling and simulation tools capable of constructing high-level models using state of the art object-oriented modeling principles. The approach is based on fundamental tree algorithms that are (even manually) applicable on implicit equation systems of long formulas, the main building blocks of model components. By applying the presented forward differentiation scheme on a given DAE, efficient representation of Sensitivity Equation Systems (SESs) is computed. Parameter sensitivities are evaluated by direct integration of the derived SESs. To overcome the runtime performance drawback of direct numerical integration, a system decomposition approach is recommended. It is shown that the runtime performance using modern variable-step integration methods tends to achieve the expected theoretical complexity of the forward differentiation scheme under few realistic assumptions. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Algorithmic differentiation Differential algebraic equations Sensitivity analysis tree algorithms Equation-based languages Modelica

来源：评论

学校读者我要写书评

暂无评论

Optimal and approximate bottleneck Steiner trees

引用

OPERATIONS RESEARCH LETTERS 1996年第5期19卷 217-224页

作者： Ganley, JL Salowe, JS QUESTECH INC FALLS CHURCH VA 22043 USA

Given a set of terminals in the plane, a bottleneck Steiner tree is a tree interconnecting the terminals, in which the length of the longest edge is minimized. The bottleneck Steiner tree problem, or special cases thereof, has applications in facility location and electronic physical design automation. In this paper, we first consider algorithms for computing optimal bottleneck Steiner trees. For a given topology, we give a direct, geometric algorithm that computes an optimal rectilinear bottleneck Steiner tree in O(n(2)) time, which improves on the time complexity of previous algorithms. We also give a linear-time algorithm that, given the output from the previous algorithm, computes a rectilinear Steiner tree with minimum bottleneck length and that, among all trees with minimum bottleneck length, has minimum total length. These topology-specific algorithms provide solutions to many facility location applications, and in combination with a topology enumeration algorithm, can be used to solve the more general problems that arise in other applications. We also describe some difficulties in generalizing these results to the Euclidean problem, and give a simple approximation algorithm for the Euclidean problem. We then consider computation of approximate bottleneck Steiner trees. Specifically, we derive the exact value of the bottleneck Steiner ratio in any distance metric. The bottleneck Steiner ratio is the maximum ratio of the length of the longest edge in a minimum spanning tree to the length of the longest edge in an optimal bottleneck Steiner tree. Thus, the bottleneck Steiner ratio indicates the quality of a minimum spanning tree as an approximation of an optimal bottleneck Steiner tree.

关键词： bottleneck Steiner trees Steiner ratio geometric algorithms tree algorithms minmax multicenter facility location

来源：评论

学校读者我要写书评

暂无评论

ON FINDING LOWEST COMMON ANCESTORS - SIMPLIFICATION AND PARALLELIZATION

引用

SIAM JOURNAL ON COMPUTING 1988年第6期17卷 1253-1262页

作者： SCHIEBER, B VISHKIN, U TEL AVIV UNIV SCH MATH SCIDEPT COMP SCIIL-69978 TEL AVIVISRAEL NYU COURANT INST MATH SCIDEPT COMP SCINEW YORKNY 10012

We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm that enables us to answer each query in $O(1)$ time, as in Harel and Tarjan [SIAM J. Comput., 13 (1984), pp. 338–355]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in $O(1)$ time using a single processor.

关键词： 05C05 68Q10 68Q20 68R10 parallel algorithms tree algorithms lowest common ancestors

来源：评论

学校读者我要写书评

暂无评论

THE CYLINDRICAL BANYAN MULTICOMPUTER - A RECONFIGURABLE SYSTOLIC ARCHITECTURE

引用

PARALLEL COMPUTING 1989年第3期10卷 319-327页

作者： MALEK, M OPPER, E Department of Electrical and Computer Engineering University of Texas at Austin Austin TX 78712 U.S.A.

A new reconfigurable systolic multicomputer architecture is presented. The proposed architecture, called the Cylindrical Banyan Multicomputer (CBM), is based on the structure of a modified banyan network where every node of the network graph is composed of an application processor, a local memory and a communication processor, and network's inputs and outputs are merged (fused). The CBM has one of the lowest (cost) X (delay) among known multicomputer architectures based on regular networks. It is shown that a variety of computation structures such as pipelines, rings, and trees may be constructed and reconfigured in an optimal or a nearby optimal way on the CBM architecture, and that various basic algorithms can be executed very efficiently in a systolic manner. It is also shown that the CBM is an easily diagnosable and fault-tolerant system.

关键词： Banyan network fault tolerance multicomputer pipeline reconfigurable system ring systolic architecture tree algorithms

来源：评论

学校读者我要写书评

暂无评论

Logical rules characterization of online consumer trust

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2021年第3期28卷 1393-1416页

作者： Andrade, Ana A. Cardoso, Margarida G. M. S. Lopes, Vitor V. Directorate Gen Energy & Geol DGEG Res Studies & Renewables Div Lisbon Portugal Inst Univ Lisboa ISCTE IUL Business Res Unit BRU IUL Lisbon Portugal Univ Lisbon CMAF CIO Fac Ciencias Lisbon Portugal

In this study, we address the discriminant factors of website trust. We specifically build sets of propositional rules that can be used to predict the level of trustworthiness of a site. Focusing on initial trust, a survey was designed to assess site characteristics observed by the respondent and his/her perceptions around appearance, reputation, fulfillment, and security. By exploring data, we look for the most favorable rules classifiers among decision trees as well as classical and dominance-based rough sets. A heuristic aiming to derive simpler classifiers is also proposed. The experimental setup considers diverse groups of attributes (predictors) for the extraction of rules. Results obtained are compared by taking into account predictive ability and parsimony of rules' sets. Finally, the selected sets help bring light on how consumers process site information and suggest specific recommendations for e-commerce vendors.

关键词： trust e‐ commerce B2C information theory rough sets tree algorithms knowledge‐ based systems

来源：评论

学校读者我要写书评

暂无评论

Robustness of Q-ary collision resolution algorithms in random access systems

引用

PERFORMANCE EVALUATION 2004年第3期57卷 357-377页

作者： Van Houdt, B Blondia, C Univ Antwerp Dept Math & Comp Sci B-2020 Antwerp Belgium

The throughput characteristics of a random access system (RAS) which uses Q-ary tree algorithms (where Q is the number of groups into which colliding users are split) of the Capetanakis-Tsybakov-Mikhailov-Vvedenskaya type are analyzed for an infinite population of identical users generating packets. In the standard model packets are assumed to be generated according to a Poisson process. In this paper we greatly relax this assumption and consider a rich class of Markovian arrival processes, which, in general, are non-renewal. This class of arrival processes is known to lend itself very well to modeling bursty and correlated arrival processes commonly arising in computer and communication applications. Blocked and grouped channel access protocols are considered in combination with Q-ary collision resolution algorithms that exploit either binary ("collision or not") or ternary ("collision, success or idle") feedback. For the resulting RASs the corresponding maximum stable throughput is determined. It is concluded that the resulting RASs maintain their good stability characteristics under the wide range of arrival processes considered, thereby further extending the theoretical foundations of tree algorithms. (C) 2004 Elsevier B.V. All rights reserved.

关键词： random access maximum stable throughput D-BMAP arrivals tree algorithms

来源：评论

学校读者我要写书评

暂无评论

A MICROCOMPUTER-BASED IMPLEMENTATION OF THE EXPANDING EQUILIBRIUM ALGORITHM FOR LINEAR, SINGLE COMMODITY SPATIAL PRICE EQUILIBRIUM PROBLEMS

引用

OPERATIONS RESEARCH LETTERS 1988年第5期7卷 241-245页

作者： THEISE, ES JONES, PC NORTHWESTERN UNIV DEPT IND ENGN & MANAGEMENT SCIEVANSTONIL 60201

We present a Turbo Pascal implementation of the expanding equilibrium algorithm for linear, single commodity spatial price equilibrium problems. We provide evidence that our microcomputer implementation is faster than a mainframe implementation of a widely-referenced alternative algorithm. An executable version of our program, with documentation, is available upon request.

关键词： spatial price equilibria large-scale systems tree algorithms complementarity problems

来源：评论

学校读者我要写书评

暂无评论

Distances in multimedia phylogeny

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2016年第5期23卷 921-946页

作者： Oikawa, Marina A. Dias, Zanoni Rocha, Anderson Goldenstein, Siome Univ Estadual Campinas Inst Comp RECOD Lab BR-13083970 Campinas SP Brazil

The distance between two objects determines how far apart they are with respect to each other. In this paper, we provide an overview of the distance concept in multimedia phylogeny, a novel research field that aims at discovering the phylogenetic relationships among digital objects that belong to the same population. With applications in digital forensics, copyright enforcement, and security, existing approaches are often based on dissimilarity computations among digital objects in a nonmetric space, but with enough information to correctly reconstruct the underlying relationships of these objects. As we discuss throughout the paper, a proper and well-designed dissimilarity is paramount for differentiating whether two multimedia objects are related and, also, the directionality of such relationship. In phylogeny setups, there is also the additional requirement of low complexity: fast and accurate dissimilarity measures to cope with the massive amount of data we often have to handle.

关键词： computing science pattern recognition information systems tree algorithms

来源：评论

学校读者我要写书评

暂无评论

O(LOG N) BIMODALITY ANALYSIS

引用

PATTERN RECOGNITION 1989年第6期22卷 741-746页

作者： PHILLIPS, TY ROSENFELD, A SHER, AC Center for Automation Research University of Maryland College Park MD 20742-3411 U.S.A

The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P1 and P2. If P is a mixture of two (approximately) Gaussian subpopulations, then P1 and P2 are good approximations to the original Gaussians, if their Fisher distance is great enough. Moreover, good approximations to P1 and P2 can be obtained by dividing P into small parts; finding the maximum-distance (MD) subdivision of each part; combining small groups of these subdivisions into (approximate) MD subdivisions of larger parts; and so on. This divide-and-conquer approach yields an approximate MD subdivision of P in O(log n) computational steps using O(n) processors, where n is the size of P.

关键词： Histograms Bimodality Fisher distance Divide-and-conquer tree algorithms Pyramid algorithms

来源：评论

学校读者我要写书评

暂无评论

SENSITIVITY ANALYSIS FOR SYMMETRICAL 2-PERIPATETIC SALESMAN PROBLEMS

引用

OPERATIONS RESEARCH LETTERS 1993年第2期13卷 79-84页

作者： DEKORT, JBJM Insttitute of Actuarial Science and Econometrics Operations Research Group Faculty of Economics and Econometrics University of Amsterdam Amsterdam Netherlands

A greedy approach can be applied to find 2 edge-disjoint 1-trees or spanning trees (if they exist) of minimum total length in a graph with n vertices and m edges. A greedy algorithm to solve the tree problem contains a routine that tests whether 2 edge-disjoint forests can be augmented with a given edge. Two test routines are discussed with different worst-case running times. The most efficient one is utilized to derive in O(m log m + n2) operations a lower bound solution to the 2-Peripatetic Salesman Problem (2-PSP), which requires 2 edge-disjoint Hamiltonian cycles of minimum total length. Then the other test routine executes in O(n2) operations a sensitivity analysis for all relevant edges. Computational results illustrate the impact of the sensitivity analysis.

关键词： GRAPHS SENSITIVITY ANALYSIS TRAVELING SALESMAN PROBLEM tree algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：