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

optimal adaptive solution of initial-value problems with unknown singularities

JOURNAL OF COMPLEXITY 2008年第4期24卷 455-476页

作者： Kacewicz, Boleslaw Przybylowicz, Pawel AGH Univ Sci & Technol Dept Appl Math PL-30059 Krakow Poland

The optima of solution of initial-value problems in ODES is well studied for smooth right-hand Side functions. Much less is known about the optimality, of algorithms for singular problems. In this paper. We Study the (worst case) solution of scalar problems with a right-hand side function having r continuous hounded derivatives in R, except for an unknown Singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The Crucial point is locating an unknown Singularity of the solution by properly adapting the grid. We also Study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r. (C) 2008 Elsevier Inc. All rights reserved.

关键词： initial-value problems singularity worst case errors optimal algorithms adaption lower bounds

来源：评论

学校读者我要写书评

暂无评论

optimal Functional-Unit Assignment for Heterogeneous Systems Under Timing Constraint

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第9期28卷 2567-2580页

作者： Jiang, Weiwen Sha, Edwin Hsing-Mean Chen, Xianzhang Yang, Lei Zhou, Lei Zhuge, Qingfeng Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China

In high-level synthesis for real-time systems, it typically employs heterogeneous functional-unit types to achieve high-performance and low-cost designs. In the design phase, it is critical to determine which functional-unit type to be mapped for each operation in a given application such that the total cost is minimized while the deadline can be met. For a path or tree structured application, existing approaches can obtain the minimum-cost assignment, called "optimal assignment", under which the resultant system satisfies a given timing constraint. However, it is still an open question whether there exist efficient algorithms to obtain the optimal assignment for the directed acyclic graph (DAG), or more generally, the data-flow graph with cycles (cyclic DFG). For DAGs, by analyzing the property of the problem, this paper designs an efficient algorithm to obtain the optimal assignments. For cyclic DFGs, we approach this problem with the combination of retiming technique to thoroughly explore the design space. We formulate a Mixed Integer Linear Programming (MILP) model to give the optimal solution. But because of the high degree of its time complexity, we devise a practical algorithm to obtain near-optimal solutions within a minute. Experimental results show the effectiveness of our algorithms. Specifically, compared with existing techniques, we can achieve 25.70 and 30.23 percent reductions in total cost on DAGs and cyclic DFGs, respectively.

关键词： Real-time heterogeneous system data-flow graphs functional-unit assignment retiming optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

On the worst-case optimal multi-objective global optimization

引用

OPTIMIZATION LETTERS 2013年第8期7卷 1921-1928页

作者： Zilinskas, Antanas Inst Math & Informat LT-08663 Vilnius Lithuania

Multi-objective optimization problem with Lipshitz objective functions is considered. It is shown that the worst-case optimal passive algorithm can be reduced to the computation of centers of balls producing the optimal cover of a feasible region, where the balls are of equal minimum radius. It is also shown, that in the worst-case, adaptivity does not improve the guaranteed accuracy achievable by the passive algorithm.

关键词： Multi-objective optimization optimal algorithms Global optimization Lipshitz optimization

来源：评论

学校读者我要写书评

暂无评论

On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization

引用

COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION 2016年第Jun.期35卷 123-136页

作者： Zilinskas, Antanas Gimbutiene, Grazina Vilnius State Univ Inst Math & Informat LT-08663 Vilnius Lithuania

The bi-objective Lipschitz optimization with univariate objectives is considered. The concept of the tolerance of the lower Lipschitz bound over an interval is generalized to arbitrary subintervals of the search region. The one-step worst-case optimality of trisecting an interval with respect to the resulting tolerance is established. The theoretical investigation supports the previous usage of trisection in other algorithms. The trisection-based algorithm is introduced. Some numerical examples illustrating the performance of the algorithm are provided. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Bi-objective optimization optimal algorithms Lipschitz optimization Trisection

来源：评论

学校读者我要写书评

暂无评论

optimal Karatsuba-like formulae for certain bilinear forms in GF(2)

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2008年第8-9期429卷 2052-2066页

作者： Oseledets, Ivan Russian Acad Sci Inst Numer Math Moscow 119333 Russia

We propose two exhaustive search-type methods for the construction of Karatsuba-like algorithms for fast computation of certain bilinear forms in GF(2). The computation is done via an explicit construction of trilinear decompositions using heuristica search algorithms. Using that approach several old and new algorithms for the fast computation of bilinear forms were obtained. (C) 2008 Elsevier Inc. All rights reserved.

关键词： optimal algorithms Karatsuba Karatsuba-Ofman polynomial multiplication trilinear decomposition tensors

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for bound and equality constrained quadratic programming problems with bounded spectrum

引用

COMPUTING 2006年第4期78卷 311-328页

作者： Dostal, Z. Tech Univ Ostrava Ostrava 70833 Czech Republic

An implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for solving the large convex bound and equality constrained quadratic programming problems is considered. It is proved that if the algorithm is applied to the class of problems with uniformly bounded spectrum of the Hessian matrix, then the algorithm finds an approximate solution at O(1) matrix-vector multiplications. The optimality results are presented that do not depend on conditioning of the matrix which defines the equality constraints. Theory covers also the problems with dependent constraints. Theoretical results are illustrated by numerical experiments.

关键词： quadratic programming bound and equality constraints augmented Lagrangians optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for Global Optimization and adaptive covering

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第3期66卷 535-572页

作者： Shishkin, Serge L. Finn, Alan M. United Technol Res Ctr 411 Silver LaneMS 129-15 E Hartford CT 06447 USA

The general class of zero-order Global Optimization problems is split into subclasses according to a proposed "Complexity measure" and the computational complexity of each subclass is rigorously estimated. Then, the laboriousness (computational demand) of general Branch-and-Bound (BnB) methods is estimated for each subclass. For conventional "Cubic" BnB based on splitting an n-dimensional cube into sub-cubes, both upper and lower laboriousness estimates are obtained. The value of the Complexity measure for a problem subclass enters linearly into all complexity and laboriousness estimates for that subclass. A new BnB method based on the lattice is presented with upper laboriousness bound that is, though conservative, smaller by a factor of than the lower bound of the conventional method. The optimality of the new method is discussed. All results are extended to the class of Adaptive Covering problems-that is, covering of a large n-dimensional set by balls of different size, where the size of each ball is defined by a locally computed criterion.

关键词： Global Optimization Branch and Bound Adaptive covering Complexity optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

AN optimal LINKED LIST PREFIX ALGORITHM ON A LOCAL MEMORY COMPUTER

引用

IEEE TRANSACTIONS ON COMPUTERS 1991年第10期40卷 1149-1153页

作者： HAN, YJ Dept. of Comput. Sci. Kentucky Univ. Lexington KY USA Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions n elements in time O(n/p+log n) on a local memory PRAM model ..." property="og:description">

We present a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefix for an input list of n elements in time O(n/p + log n) on a local memory PRAM model using p processors a... 详细信息

关键词： GRAPH algorithms LINKED LIST LOCAL MEMORY COMPUTER MEMORY SHARING optimal algorithms PARALLEL algorithms PREFIX

来源：评论

学校读者我要写书评

暂无评论

optimal MULTISTAGE ALGORITHM FOR ADJOINT COMPUTATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第3期38卷 C232-C255页

作者： Aupy, Guillaume Herrmann, Julien Hovland, Paul Robert, Yves ENS Lyon INRIA LIP F-69364 Lyon 07 France Vanderbilt Univ 221 Kirkland Hall Nashville TN 37235 USA Argonne Natl Lab 9700 S Cass Ave Argonne IL 60439 USA Univ Tennessee Knoxville TN 37996 USA

We reexamine the work of Stumm and Walther on multistage algorithms for adjoint computation. We provide an optimal algorithm for this problem when there are two levels of checkpoints, in memory and on disk. Previously, optimal algorithms for adjoint computations were known only for a single level of checkpoints with no writing and reading costs;a well-known example is the binomial checkpointing algorithm of Griewank and Walther. Stumm and Walther extended that binomial checkpointing algorithm to the case of two levels of checkpoints, but they did not provide any optimality results. We bridge the gap by designing the first optimal algorithm in this context. We experimentally compare our optimal algorithm with that of Stumm and Walther to assess the difference in performance.

关键词： optimal algorithms checkpointing adjoint computation program reversal automatic differentiation

来源：评论

学校读者我要写书评

暂无评论

Finding optimal solutions to several gray pattern instances

引用

OPTIMIZATION LETTERS 2022年第2期16卷 713-722页

作者： Drezner, Zvi Kalczynski, Pawel Misevicius, Alfonsas Palubeckis, Gintaras Calif State Univ Fullerton Coll Business & Econ Fullerton CA 92834 USA Kaunas Univ Technol Dept Multimedia Engn Kaunas Lithuania

In this paper we compare two new binary linear formulations to a standard quadratic binary program for the gray pattern problem and solved all three by the Gurobi solver. One formulation performed significantly better and obtained seven optimal solutions that were not proven optimal before. It is interesting that the formulation that performed best is based on significantly more variables and constraints.

关键词： optimal algorithms Quadratic assignment problem Gray pattern

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：