Application of sparse matrix techniques to inter-regional input-output analysis
Tóm tắt
Combining the concepts described in this paper makes it possible to solve inter-regional input-output systems (and other types of large, sparse, linear systems) with considerable efficiency in storage and computation. The exact number of operations and corresponding savings in computational time and storage depend on the particular zero-non zero structure of each matrix in the system, but in any case the savings can be enormous. A recommended procedure is summarized below. 1. Take the entire inter-regional IO system which includes the representation of each of the regions and of the links among them and express it in the formMx=Bz or, more simply,Mx=b (since bothB andz are known). It may be helpful for this purpose to draw a picture of the large matrixM. 2. PartitionM into blocks, exploiting the structure of the particular system. For example, at the very least, the matrix or matrices corresponding to each region will probably be separate blocks. The analysis required for this step may lead to reformulating the matrix representation of the given economic system by, for example, replacing a set of equations with linear combinations of these same equations, particularly for the equations representing the links among regions. 3. Identify an appropriate partition of the blocks ofM, and a corresponding partition of the vectorsx andb, for performing a block factorization. This solution algorithm, which solves forx inMx=b (whereM now represents the entire system) is not available as a packaged program and so for the foreseeable future must be written in ‘home-made’ computer code that assumes a sparse matrix storage scheme compatible with the package to be used (as in 4 below). The algorithm for block factorization in the 2×2 case relevant to our particular inter-regional IO system is given in Section 8 of this paper. 4. Some steps of the algorithm require solving smaller systems of the formHu=v foru, given some matrixH and some vectorv. Efficient packaged subroutines can be obtained at low cost in order to solve these systems by finding the block triangular form corresponding to a particularH, then performing theLU factorization of the diagonal blocks only. The home-made code will interact with these subroutines.
Tài liệu tham khảo
AlmonC., BucklerM. B., HorwitzL. M., and ReimboldT. C.1985: Interindustry Forecasts of the American Economy, Lexington Books, Heath and Company, Lexington, Mass., 1974.
Buckler, M. B., Personal communication, 1978.
DuffI. S., ReidJ. K., ‘An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix,’ACM Transactions of Mathematical Software, Vol. 4 (1978) pp. 137–147.
DuffI. S., ‘MA28 — a set of FORTRAN subroutines for sparse unsymmetric systems of linear equations,’ A.E.R.E. Report R. 8730, Her Majesty's Stationery Office, London, 1977.
EamesC. and EamesR.,A Computer Perspective, Harvard University Press, Cambridge, Mass., 1973.
Eisenstat, S. C., Gursky, M. C., Shultz, M. M., and Sherman, A. M., ‘Yale Sparse Matrix Package (I-The symmetric code, II-The non-symmetric code),’ Research Reports #112, 114, Yale University, Department of Computer Science, 1977.
ForsytheG., and MolerC. B.,Computer Solution of Linear Algebraic Systems, Prentice Hall, Englewood Cliffs, 1976.
GeorgeA., ‘On block elimination for sparse linear systems,’SIAM Journal on Numerical Analysis, Vol. 11 (1974), pp. 585–603.
GustavsonF., ‘Finding the block lower triangular form of a sparse matrix,’ inSparse Matrix Computations (BunchJ. and RoseD., eds.), Academic Press, New York, 1976.
LeontiefW., ‘The Structure of Development (1936),’ inInput-Output Economics, Oxford University Press, New York, 1966.
LeontiefW., CarterA., and PetriP.,The Future of the World Economy, Oxford University Press, New York, 1977.
LINPACK, User's Guide, SIAM, Philadelphia, Pennsylvania 1979.
Noh, K., and Sameh, A., ‘Computational Techniques for Input-Output Econometric Models,’ Center for Advanced Computation No. 134, University of Illinois at Urbana-Champaign, 1974.
Petri, Peter, ‘Guide to the Operation of the United Nations World Model, Technical Report No. 3,’ Department of Economics and Brandeis Economic Research Center, Brandeis University, August, 1977.
Reid, J. K., ‘Solution of Linear Systems of Equations: Direct Methods,’ inSparse Matrix Techniques, Copenhagen, 1976, Lecture Notes in Mathematics #572.
SL-MATH, IBM System/360 and System/370, IBM 1130 and IBM 1800 Subroutine Library-Mathematics, User's Guide (Program Product 5736-XM7 and 5711-XM2), Second Edition, 1974.
StrangG.,Linear Algebra and its Applications, Academic Press, New York, 1976.
Szyld, D., ‘Preliminary Report on the Numerical Treatment of the Model of the World Economy,’ Unpublished manuscript, 1978.