Resource Center

Advanced Search
Technical Papers
Working Papers
Research Memoranda
GTAP-L Mailing List
GTAP FAQs
CGE Books/Articles
Important References
Submit New Resource

GTAP Resources: Resource Display

GTAP Resource #5796

"Improving the Performance of sparse LU Decomposition in GEMPACK"
by Schiffmann, Florian and Michael Jerie


Abstract
In GEMPACK the computational general equilibrium (CGE) model is solved in its linearized form.In this form, the solution to the CGE model is computed by solving a sparse non symmetric linear system of equations(LSE). In most computer programs, the solution to a LSE is computed either by using matrix decomposition methods (direct), iterative methods or subspace methods. GEMPACK employs a sparse LU decomposition with iterative refinement to solve the LSE. Until GEMPACK 12 these solvers purely relied on algorithms from the Harwell Subroutine Library (HSL) with MA48 as the default solver. While computationally efficient, computing the LU decomposition using these off-the-shelf routines remained the time limiting step for many CGE models.
In this paper, we will present a new algorithm for the analysis phase and other improvements to the original HSL routines which greatly improve the solution time for most CGE problems. The preparation stage for the analysis phase involves the reorganisation of the matrix into strong components. By replacing the original modified Hopcroft-Karp algorithm with a tree grafting algorithm to determine a suitable bipartite matching the relative time spent can be reduced by a large factor. The most time consuming part in the analysis phase is the determination of a suitable pivot structure.
We developed series of buffered sorted data structures, lower bound estimates and an on-the-fly partitioning of the matrix into sparse and full processed parts which efficiently handles this problem. The new algorithm is able to find a suitable pivot structure with lower number of fill-ins at a significantly reduced cost than the original MA48 solver. For the most common CGE problems we see reductions in solution time by a factor 5 to 10.


Resource Details (Export Citation) GTAP Keywords
Category: 2019 Conference Paper
Status: Published
By/In: Presented at the 22nd Annual Conference on Global Economic Analysis, Warsaw, Poland
Date: 2019
Version:
Created: Schiffmann, F. (4/15/2019)
Updated: Schiffmann, F. (4/15/2019)
Visits: 678
- Software


Attachments
If you have trouble accessing any of the attachments below due to disability, please contact the authors listed above.


Public Access
  File format GTAP Resource 5796  (144.6 KB)   Replicated: 0 time(s)


Restricted Access
No documents have been attached.


Special Instructions
No instructions have been specified.


Comments (0 posted)
You must log in before entering comments.

No comments have been posted.