Browsing by Author "Chakraborty, Amal"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Analysis of Function Component Complexity for Hypercube Homotopy Algorithms
    Chakraborty, Amal; Allison, Donald C. S.; Ribbens, Calvin J.; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    Probability-one homotopy algorithms are a class of methods for solving nonlinear systems of equations that globally convergent from an arbitrary starting point with probability one. The essence of these homotopy algorithms is the construction of a homotopy map p-sub a and the subsequent tracking of a smooth curve y in the zero set p-sub a to the -1 (0) of p-sub a. Tracking the zero curve y requires repeated evaluation of the map p-sub a, its n x (v + 1) Jacobian matrix Dp-sub a and numerical linear algebra for calculating the kernel of Dp-sub a. This paper analyzes parallel homotopy algorithms on a hypercube, considering the numerical algebra, several communications topologies and problem decomposition strategies, functions component complexity, problem size, and the effect of different component complexity distributions. These parameters interact in complicated ways, but some general principles can be inferred based on empirical results.
  • Thumbnail Image
    Analysis of Function Component Complexity for Hypercube Homotopy Algorithms
    Chakraborty, Amal; Allison, Donald C. S.; Ribbens, Calvin J.; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1991)
    Probability-one homotopy algorithms are a class of methods for solving nonlinear systems of equations that are globally convergent from an arbitrary starting point with probability one. The essence of these homotopy algorithms is the construction of a homotopy map ra and the subsequent tracking of a smooth curve g in the zero set ra-1 (0) of ra . Tracking the zero curve g requires repeated evaluation of the map ra its n x (n + 1) Jacobian matrix Dra , and numerical linear algebra for calculating the kernel of Dra . This paper analyzes parallel homotopy algorithms on a hypercube, briefly reviewing the numerical linear algebra, several communication topologies and problem decomposition strategies, and concentrating on function component complexity, problem size, and the effect of different component complexity distributions. These parameters interact in complicated ways, but some general principles can be inferred based on empirical results. Implications for developing reliable and efficient parallel mathematical software packages for this problem area are also discussed.
  • Thumbnail Image
    Granularity Issues for Solving Polynomial Systems via Globally Convergent Algorithms on a Hypercube
    Allison, Donald C. S.; Chakraborty, Amal; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988-05-01)
    Polynomial systems of equations frequently arise in many applications such as solid modeling, robotics, computer vision, chemistry, chemical engineering, and mechanical engineering . Locally convergent iterative methods such as quasi-Newton methods may diverge or fail to find all meaningful solutions of a polynomial system. Recently a homotopy algorithm has been proposed for polynomial systems that is guaranteed globally convergent (always converges from an arbitrary starting point) with probability one, finds all solutions to the polynomial system, and has a large amount of inherent parallelism. There are several ways the homotopy algorithms can be decomposed to run on a hypercube. The granularity of a decomposition has a profound effect on the performance of the algorithm. The results of decompositions with two different granularities are presented. The experiments were conducted on an iPSC-16 hypercube using actual industrial problems.
  • Thumbnail Image
    An integrated computer simulator for surface mine planning and design
    Chakraborty, Amal (Virginia Polytechnic Institute and State University, 1985)
    In the increasingly competitive coal market, it is becoming more important for coal operators to develop mathematical models for surface mining which can estimate mining costs before the actual mining begins. The problem becomes even more acute with the new reclamation laws, as they affect surface coal mining methods, productivity, and costs. This study presents a computer simulator for a mountaintop removal type of surface mining operation. It will permit users to compare the costs associated with different overburden handling and reclamation plans. It may be used to minimize productivity losses, and, perhaps, to increase productivity and consequently to reduce operating costs through design and implementation of modified mountain top removal methods.
  • Thumbnail Image
    Parallel homotopy curve tracking on a hypercube
    Chakraborty, Amal (Virginia Tech, 1990-05-06)
    Probability-one homotopy methods are a class of methods for solving non-linear systems of equations that are globally convergent with probability one from an arbitrary starting point. The essence of these algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy zero curve requires calculating the unit tangent vector at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map ρα(λ,x) is in the one-dimensional kernel of the full rank n x (n + 1) Jacobian matrix Dρα(λ,x). Hence, tracking a zero curve of a homotopy map involves evaluating the Jacobian matrix and finding the one-dimensional kernel of the n x (n + 1) Jacobian matrix with rank n. Since accuracy is important, an orthogonal factorization of the Jacobian matrix is computed. The QR and LQ factorizations are considered here. Computational results are presented showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube, in the context of parallel homotopy algorithms for problems with small, dense Jacobian matrices. This study also examines the effect of different component complexity distributions and the size of the Jacobian matrix on the different assignments of components to the processors, and determines in what context one assignment would perform better than others.
  • Thumbnail Image
    Unit Tangent Vector Computation for Homotopy Curve Tracking on aHypercube
    Chakraborty, Amal; Allison, Donald C. S.; Ribbens, Calvin J.; Watson, Layne T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)
    Probability-one homotopy methods are a class of methods for solving nonlinear systems of equations that are globally convergent from an arbitrary starting point. The essence of all such algorithms is the construction of an appropriate homotopy map and subsequent tracking of some smooth curve in the zero set of the homotopy map. Tracking a homotopy curve involves finding the unit tangent vectors at different points along the zero curve. Because of the way a homotopy map is constructed, the unit tangent vector at each point in the zero curve of a homotopy map (symbols) is in the kernel of the Jacobian matrix (symbols). Hence tracking the zero curve of a homotopy map involves finding the kernel of the Jacobian matrix (symbols). The Jacobian matrix (symbols) is a n x (n + 1) matrix with full rank. Since the accuracy of the unit tangent vector is very important, on orthogonal factorization instead of an LU factorization of the Jacobian matrix is computed. Two related factorizations, namely QR and LQ factorization, are considered here. This paper presents computational results showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms on a hypercube. Since the purpose of this study is to find ways to parallelize homotopy algorithms, it is assumed that the matrices are small, dense, and have a special structure such as that of the Jacobian matrix of a homotopy map.