DIMACS
DIMACS REU 2013

General Information

me
Student: Thomas Gibson
Office: CoRE 434
School: Baylor University
E-mail: Thomas_Gibson@baylor.edu
Project: Applications of the Triangle Algorithm to Systems of Linear Equations

Project Description

Dr. Kalantari's Triangle Algorithm is an iterative method that approximates a distinguished point p in the convex hull of a set in an m-dimensional space. Based on a simple, yet powerful theorem, the notion of distance duality plays an important role in the convex hull decision problem. Our goal is to incorporate the triangle algorithm in an iterative method for solving systems of linear equations. Our hope is that the new geometric approach will provide a viable algorithm for solving systems of linear equations in comparison to traditional methods such as Jacobi, Gauss-Seidel, and Krylov methods. We also seek to apply the triangle algorithm in the context of eigenvalue problems and develop an algorithm for computing specific eigenvalues.


Weekly Log

Week 1:
I arrived at Rutgers campus from New York and met with my mentor, Dr. Bahman Kalantari, to discuss the direction of my project. He wanted me to investigate his Triangle Algorithm as an iterative method for solving systems of linear equations. I spent most of the week reading relevant background literature and gain a full understanding of my topic. Due to my background in numerical linear algebra, he suggested that I look into applying this algorithm as an iterative method for both systems of equations and eigenvalue problems. I eagerly accepted and presented my problem to the REU program on Friday, June 7th.
Week 2:
I have coded a rough "skeleton" of the Triangle algorithm that seeks to approximate a point, p, within the convex hull of a set. I have noticed that, in its basic form, the algorithm is not very efficient and I have come up with examples where the algorithm performs at its worst. I have come up with ideas to improve the efficiency of the algorithm. Once I have written an effective convex hull algorithm, I will begin to incorporate the Triangle algorithm into an iterative method to solve a linear system of equations.
Week 3:
I have continued on the progress of week 2. I have written an algorithm that allows me to track the path of the iterate within the convex hull at each iteration. The program allows me to visually see how the iterate behaves based on the location of the distinguished point p. I have some pictures of when convergence is both fast and slow for the Triangle Algorithm. Slow convergence is a result of the point p lying almost in between a line segment joining two vertices. I have thought of some ways to target the problem areas and am working on a stable algorithm that fixes the case for slow convergence. I was suggested to think about taking a midpoint between vertices and the point p to create new pivots.
Week 4:
I have successfully improved the triangle algorithm by implementing angle checking and the addition of auxiliary pivot points. I have received some sample systems of equations that I can start working on in an attempt to use the triangle algorithm in the context of equation solving. My current obstacle is keeping track of the convex coefficients of the iterate so that I can use the information in solving systems of equations. I have successful implementations of Jacobi, Gauss-Seidel, SOR, and conjugate gradient method to compare with the triangle algorithm iteration. Once I have taken care of the issue I'm having, I will start running numerical tests.
Week 5:
I have written a program, utilizing the triangle algorithm, that solves a system of linear equations. For small systems, the program out performs Jacobi, Gauss-Seidel, and SOR with an optimal relaxation coefficient. It performs as well as, but not better than, the GMRES Krylov method on certain example systems. So far, this is the case for nonnegative solutions. I am currently working on adapting the algorithm to work on larger systems of equations. This is proving to be fairly complicated.
Week 6:
I recoded several versions of the triangle algorithm in MatLab and have generated visual examples of both 2D and 3D convex hull settings. The triangle algorithm performs very well in the context of point-finding within a convex hull. However, in the context of linear systems of equations, it is not the case. I have observed the algorithm taking many iterations and sometimes never converging in high dimensional systems. The triangle algorithm solves the 2xm and 3xm cases very well. However as n increases, the number of iterations increase. This presents a new problem where I believe the density of points matters. Higher dimension systems presents a challenging problem for the triangle algorithm and needs improvement. I have brought this up with both my graduate mentor and Dr. Kalantari. I have been given a new idea for adding auxiliary pivots that I will try to implement before my final presentation in this upcoming week. I still believe that while the algorithm doesn't perform well in high dimensional systems, it is flexible and can be improved.
Week 7:
I recorded some examples for my final presentation this week. I generated some visualizations of both 2D and 3D convex hulls. Most of the week was spent learning LaTeX for my last presentation on July 19th. The presentation went alright, though I ran out of time towards the end. I am working on implementing the incremental triangle algorithm and am collecting information to put into my final report.

Presentations


Additional Information