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

parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2005年第2期27卷 687-713页

作者： Biros, G Ghattas, O NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA Carnegie Mellon Univ Dept Biomed Engn Ultrascale Simulat Lab Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Civil & Environm Engn Ultrascale Simulat Lab Pittsburgh PA 15213 USA

Large-scale optimization of systems governed by partial differential equations ( PDEs) is a frontier problem in scientific computation. Reduced quasi-Newton sequential quadratic programming (SQP) methods are state-of-the-art approaches for such problems. These methods take full advantage of existing PDE solver technology and parallelize well. However, their algorithmic scalability is questionable;for certain problem classes they can be very slow to converge. In this two-part article we propose a new method for steady-state PDE-constrained optimization, based on the idea of using a full space Newton solver combined with an approximate reduced space quasi-Newton SQP preconditioner. The basic components of the method are Newton solution of the first-order optimality conditions that characterize stationarity of the Lagrangian function;Krylov solution of the Karush - Kuhn - Tucker ( KKT) linear systems arising at each Newton iteration using a symmetric quasi-minimum residual method;preconditioning of the KKT system using an approximate state/decision variable decomposition that replaces the forward PDE Jacobians by their own preconditioners, and the decision space Schur complement ( the reduced Hessian) by a BFGS approximation initialized by a two- step stationary method. Accordingly, we term the new method Lagrange - Newton - Krylov - Schur (LNKS). It is fully parallelizable, exploits the structure of available parallel algorithms for the PDE forward problem, and is locally quadratically convergent. In part I of this two- part article, we investigate the effectiveness of the KKT linear system solver. We test our method on two optimal control problems in which the state constraints are described by the steady-state Stokes equations. The objective is to minimize dissipation or the deviation from a given velocity field;the control variables are the boundary velocities. Numerical experiments on up to 256 Cray T3E processors and on an SGI Origin 2000 include scalability and

关键词： sequential quadratic programming adjoint methods PDE constrained optimization optimal control Lagrange-Newton-Krylov-Schur methods Navier-Stokes finite elements preconditioners indefinite systems nonlinear equations parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel preconditioners for heat transfer applications on ANU-cluster

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第3期163卷 1243-1263页

作者： Kumar, BVR Kumar, B Indian Inst Technol Dept Math Parallel Comp Lab Kanpur 208016 Uttar Pradesh India

In this study we discuss in detail various strategies involved in evolving MIMD parallel algorithms for preconditioners such as ILU, SSOR, etc., on a cluster of PCs under ANULIB message passing environment. The task flow graphs used as logical basis in designing parallel algorithms are introduced. parallel preconditioners are used in accelerating the convergence of Krylov solvers such as GMRES, CGM. The preconditioned iterative solvers are tested for performance on heat transfer applications such as (a) convection in trapezoidal and square porous enclosure and (b) reaction-diffusion problem, etc. (c) 2004 Published by Elsevier Inc.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel factorization and solution of structured and unstructured linear systems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2005年第1期71卷 86-143页

作者： Reif, JH Duke Univ Dept Comp Sci Durham NC 27708 USA

This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the corresponding linear systems (which need not be SPD), and for finding rank and determinant magnitude. We assume the input matrices have entries that are rational numbers expressed as a ratio of integers with at most a polynomial number of bits beta. We assume a parallel random access machine (PRAM) model of parallel computation, with unit cost arithmetic operations, including division, over a finite field Z(p), where p is a prime number whose binary representation is linear in the size of the input matrix and is randomly chosen by the algorithm. We require only bit precision O(n(beta + log n)), which is the asymptotically optimal bit precision for beta >= log n. Our algorithms are randomized, giving the outputs with high likelihood >= 1 - 1/n(Omega(1)). We compute LU and QR factorizations for dense matrices, and LU factorizations of sparse matrices which are s(n)-separable, reducing the known parallel time bounds for these factorizations from Omega(log(3) n) to O(log(2) n), without an increase in processors (matching the best known work bounds of known parallel algorithms with polylog time bounds). Using the same parallel algorithm specialized to structured matrices, we compute LU factorizations for Toeplitz matrices and matrices of bounded displacement rank in time O(log(2) n) with n log log n processors, reducing by a nearly linear factor the best previous processor bounds for polylog times (however, these prior works did not generally require unit cost division over a finite field). We use this result to solve in the same bounds: polynomial resultant;and Pade approximants of rational functions;and in a factor O(log n) more time: polynomial greatest common divisors (GCD) and extended GCD;again reducing the best process

关键词： parallel algorithms linear systems LU factorization dense matrices sparse matrices Newton iteration structured matrices Toeplitz matrices displacement rank polynomial greatest common divisors GCD resultant Pade approximation

来源：评论

学校读者我要写书评

暂无评论

Sampling-based roadmap of trees for parallel motion planning

引用

IEEE TRANSACTIONS ON ROBOTICS 2005年第4期21卷 597-608页

作者： Plaku, E Bekris, KE Chen, BY Ladd, AM Kavraki, LE Rice Univ Dept Comp Sci Houston TX 77005 USA

This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampting-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRIM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.

关键词： expansive space trees (EST) motion planning parallel algorithms probabilistic roadmap method (PRM) rapidly exploring random trees (RRT) roadmap sampling-based planning sampling-based roadmap of trees (SRT) tree

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for static program slicing

引用

International Journal of Information and Management Sciences 2005年第2期16卷 35-46页

作者： Mishra, P.K. Birla Institute of Technology India Dept. of Applied Mathematics Birla Institute of Technology Mesra Ranchi-835215 India

Program slicing is the process of deleting statements in a program that do not affect a given set of variables at a chosen point in the program. In this paper the parallel slicing algorithm is introduced. It is shown how the control flow graph of the program to be sliced is converted into a network of concurrent processes, thereby producing a parallel version of Weiser's original static slicing algorithm. Keywords:.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

BSPC: A novel bitmap-based scalable parallel classifier

引用

AEJ - Alexandria Engineering Journal 2005年第4期44卷 585-595页

作者： Drahem, Ghada H. Abougabal, Mohamed S. Sueyllam, Hesham Mahar, Khaled M. Computer Science and Automatic Control Dept. Faculty of Eng. Alexandria University Alexandria Egypt College of Computing and Information Technology ASST Alexandria Egypt

Decision trees have been found very effective for classification especially in data mining. Although classification is a well studied problem, most of the current classification algorithms need an in-memory data structure to achieve efficiency. This limits their suitability for mining over large databases. In this paper, a novel Bitmap-based Scalable parallel Classifier (BSPC) is presented. It removes all the memory requirements needed by existing algorithms. Also, since scalability is a key requirement for any data mining algorithm, it is considered and achieved in the design of BSPC. Additionally, the suggested algorithm has been designed to be easily parallelized, allowing many processors to work together to build a single consistent model. Performance analysis demonstrates that the BSPC outperforms other state of the art algorithms. The superiority of the novel algorithm is demonstrated through the classification of Wisconsin breast cancer dataset. © Faculty of Engineering Alexandria University.

关键词： Algorithm complexity analysis Bitmap index Classification Data mining Decision tree parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Information exchange in asynchronous parallel simplex algorithm

Elektrotehniski Vestnik/Electrotechnical Review

引用

Elektrotehniski Vestnik/Electrotechnical Review 2005年第4期72卷 231-236页

作者： Burmen, Arpad Tuma, Tadcj University of Ljubljani Faculty of Electrical Engineering Tržaška 25 1000 Ljubljana Slovenia

Automated parametric design is becoming an important issue in engineering. Especially in analog integrated circuit design this trend is becoming more and more obvious. Parametric optimization is a key element of automated parametric design. For the reason of computational complexity of the cost function evaluation (which is usually simulation based) optimization can take a lot of time even for solving small design problems. One of the possible ways for attacking the computational complexity of the typical optmization problems is the use of parallel optimization algorithms. Two large families of such algorithms exist: synchronous and asynchronous algorithms. Due to their flexibility and efficiency asynchronous algorithms are becoming a viable option for parallel optimization. An asynchronous parallel simplex algorithm for unconstrained minimization is presented based on the convergent variant of the Nelder-Mead simplex algorithm. Several different approaches to information exchange between workers in a parallel asynchronous optimization system are discussed and evaluated on a set of testbench unconstrained optimization problems. Speedup results are presented for the best-performing information exchange algorithm. The results show a significant speedup for moderately dimensional optimization problems. The defficiencies of the algorithm are discussed and guidelines for future work are given.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Provable algorithms for parallel sweep scheduling on unstructured meshes

Provable algorithms for parallel sweep scheduling on unstruc...

引用

International Symposium on parallel and Distributed Processing (IPDPS)

作者： V.S. Anil Kumar M.V. Marathe S. Parthasarathy A. Srinivasan S. Zust MSM997 Los Alamos National Laboratory Los Alamos NM USA Virginia Bio-Informatics Institute and Department of Computer Science Virginia Polytechnic Institute and State University Blacksburg VA USA Department of Computer Science University of Maryland College Park MD USA Department of Computer Science and UMIACS University of Maryland College Park MD USA

We present provably efficient parallel algorithms for sweep scheduling on unstructured meshes. Sweep scheduling is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Several heuristics have been proposed for this problem; but none of the heuristics have worst case performance guarantees. We present a simple, almost linear time randomized algorithm which (provably) gives a schedule of length at most O(log/sup 2/n) times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length O(logmlogloglogm) times the optimal schedule for m processors. These are the first such provable guarantees for this problem. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice. We complement our theoretical results with extensive empirical analysis. The results show that (i) our algorithm performs very well and has significantly better performance guarantee in practice and (ii) the algorithm compares favorably with other natural and efficient parallel algorithms proposed in the literature [S. Pautz, (2002), S. Plimpton et al., (2001)].

关键词： Scheduling algorithm Processor scheduling Optimal scheduling Computer science Distributed computing Laboratories Educational institutions parallel algorithms Algorithm design and analysis Cost function

来源：评论

学校读者我要写书评

暂无评论

An experimental study of parallel biconnected components algorithms on symmetric multiprocessors (SMPs)

An experimental study of parallel biconnected components alg...

引用

International Symposium on parallel and Distributed Processing (IPDPS)

作者： G. Cong D.A. Bader IBM Thomas J. Watson Research Center Yorktown Heights NY USA Department of Electrical and Computer Engineering University of New Mexico Albuquerque NM USA

We present an experimental study of parallel biconnected components algorithms employing several fundamental parallel primitives, e.g., prefix sum, list ranking, sorting, connectivity, spanning tree, and tree computations. Previous experimental studies of these primitives demonstrate reasonable parallel speedups. However, when these algorithms are used as subroutines to solve higher-level problems, there are two factors that hinder fast parallel implementations. One is parallel overhead, i.e., the large constant factors hidden in the asymptotic bounds; the other is the discrepancy among the data structures used in the primitives that brings non-negligible conversion cost. We present various optimization techniques and a new parallel algorithm that significantly improve the performance of finding biconnected components of a graph on symmetric multiprocessors (SMPs). Finding biconnected components has application in fault-tolerant network design, and is also used in graph planarity testing. Our parallel implementation achieves speedups up to 4 using 12 processors on a Sun E4500 for large, sparse graphs, and the source code is freely-available at our Web site.

关键词： Switched-mode power supply parallel algorithms Phase change random access memory Sorting Concurrent computing Testing Data structures Costs Fault tolerance Sun

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms of hypercomplex calculations: parallel approach

Fast algorithms of hypercomplex calculations: parallel appro...

引用

International Symposium on Image and Signal Processing and Analysis

作者： M. Chicheva M. Aliev A. Yershov Image Processing Systems Institute of the RAS Samara Russia Adygeya State University Maikop Russia Samara State University Samara Russia

We consider technique for parallelization of computation with hypercomplex numbers in multidimensional space for signal processing purposes. In particular, parallel algorithms of the multidimensional hypercomplex disc... 详细信息

关键词： Algebra Multidimensional systems Concurrent computing Discrete Fourier transforms Multidimensional signal processing Signal processing algorithms parallel algorithms Signal processing Filtration Tellurium

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：