| EPSRC Reference: |
GR/S69092/01 |
| Title: |
Visit to Parallel Algorithms Group, CERFACS, Toulouse, France |
| Principal Investigator: |
Hall, Dr J |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Mathematics |
| Organisation: |
University of Edinburgh |
| Scheme: |
Overseas Travel Grants Pre-FEC |
| Starts: |
01 August 2003 |
Ends: |
31 January 2004 |
Value (£): |
2,800
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Mathematical Aspects of OR |
| Parallel Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Although the improvement in computational efficiency when exploiting hyper-sparsity in the revised simplex method can be huge, it is typically limited by the cost of the (small) proportion of simplex iterations in which hyper-sparsity is not exhibited. I will investigate the extent to which such iterations can be identified a priori and develop alternative column and row selection strategies which reduce their occurrence. This is expected to lead to further significant improvements in computational efficiency. Our technique for exploiting hyper-sparsity when solving linear systems of equations within the revised simplex method is purely heuristic, although it performs very well in practice. However, an efficient implementation of the algorithm of Gilbert and PARSMI may give better performance, in particular on very large problems. I will develop such an implementation, tuning it for the revised simplex method, and perform a comparison with our current approach. We developed the PARSMI algorithm in the light of our experience with our ASYNPLEX algorithm and results obtained (using a restricted and time-consuming implementation on a distributed memory Cray T3D) were encouraging. Shared memory multiprocessors, upon which implementation of PARSMI would be much easier, are now more widely available so I will develop such an implementation.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.ed.ac.uk |