LIBRARY OF THE 
 
 UNIVERSITY OF ILLINOIS 
 
 AT URBANA-CHAMPAICN 
 
 510.84 
 
 I&63c 
 no.£>l-70. 
 
AUG. 31.976 
 
 ihe person charging this material is re- 
 sponsible for its return to the library from 
 which it was withdrawn on or before the 
 Latest Date stamped below. 
 
 Theft, mutilation, and underlining of books 
 are reasons for disciplinary action and may 
 result in dismissal from the University. 
 
 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN 
 
 I 
 
 r*ait$ ft 
 
 om 
 
 
 - 
 
 JAM 
 
 APR 8 
 
 Wl8\ 
 
 
 ro »fe 
 
 
 
 OCT 
 
 kc 
 
 PHOTO REPRODICTION 
 
 OCT 22SECTJ 
 
 PHOTO REPRODUCTION 
 
 NOV 1 6 fa** 
 
 REPRODUCE* 
 
 1 BJ 
 
 lh\ 
 
 2 7 «EC1 
 
 rfER00C !r - 
 
 I 3 REtTO 
 
 L161 — O-1096 
 
Digitized by the Internet Archive 
 
 in 2012 with funding from 
 
 University of Illinois Urbana-Champaign 
 
 http://archive.org/details/methodsforincrea66same 
 

fcji£in 
 
 CONFERENCE ROOM 
 
 ENGINEERING LIBRARY 
 UN1V V Or )IS 
 
 1MB AN A, 
 
 enter for Advanced Computation 
 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 URBANA. ILLINOIS 61801 
 
 CAC Document No. 66 
 
 METHODS FOR INCREASING THE COMPUTATIONAL 
 EFFICIENCY OF INPUT-OUTHJT AND RELATED 
 LARGE SCALE MATRIX OPERATIONS 
 
 Ahmed H. Sameh and Roger H. Bezdek 
 
CAC Document No. 66 
 
 METHODS FOR INCREASING THE COMPUTATIONAL 
 EFFICIENCY OF INPUT-OUTPUT AND RELATED 
 LARGE SCALE MATRIX OPERATIONS 
 
 By 
 
 Ahmed H. Sameh 
 
 and 
 Roger H. Bezdek 
 
 Center for Advanced Computation 
 University of Illinois at Urb ana-Champaign 
 Urbana, Illinois 6l801 
 
 February 1973 
 
 This work was supported in part by the Advanced Research 
 Projects Agency of the Department of Defense and was 
 monitored by the U.S. Army Research Office-Durham under 
 Contract No. DAHC0U-72-C-0001. 
 
ENGINEERING UBRAHI 
 
 ABSTRACT 
 
 This paper develops numerical methods for greatly increas- 
 ing the computational efficiency of input-output and related large 
 scale matrix operations. Once the Leontief inverse matrix is com- 
 puted according to the algorithm specified here, these methods permit 
 the accurate determination of the effects on the inverse coefficients 
 of changes in the transaction data with far fever operations than 
 required to compute the inverse "from scratch". These techniques 
 are demonstrated by considering modifications down a column of the 
 direct coefficients matrix, modifications along a row of the direct 
 coefficients matrix, and disaggregation of the industries in the new 
 system. The very large gains in efficiency of this method are indi- 
 cated and the implications of these techniques for empirical and 
 theoretical input-output research are briefly discussed. 
 
ACKNOWLEDGEMENT 
 
 Ahmed Sameh is Assistant Professor in the Department of 
 Computer Science and the Center for Advanced Computation, University 
 of Illinois at Urban a- Champaign. Roger H. Bezdek is Assistant 
 Professor in the Department of Economics, the Institute of Labor 
 and Industrial Relations, and the Center for Advanced Computation. 
 The authors are grateful to Jonathan Lermit and Daniel Slotnick for 
 helpful comments on this paper, but retain sole responsibility for 
 the opinions expressed here and for any errors. This work was 
 supported in part by the Advanced Research Projects Agency of the 
 Department of Defense under Contract No. DAHC01+-72-C-0001 to the 
 Center for Advanced Computation. 
 
I. INTRODUCTION 
 
 When input-output analysis was first developed, the compu- 
 tational problems involved in interindustry economics were formidable, 
 due to the relatively primitive state of the electronic computers 
 then in existence. In the 1950 's a literature evolved concerning 
 various ways of handling input-output data so as to minimize the 
 actual computations involved, but recent advances in computer techno- 
 logy have greatly decreased the significance of computational problems 
 for most interindustry work. Nevertheless, the detailed BEA 1963 
 input-output table contained U78 industries and work with matrices of 
 this order still can present serious computational and financial 
 problems. Further, computing costs can present a problem even with 
 
 interindustry systems far more aggregate if coefficient changes neces- 
 sitate the frequent recomputation of the leontief inverse. 
 
 In this paper we develop methods for accurate calculation 
 of the effects of changes in the original transactions matrix on 
 the inverse coefficients which do not require the recomputation of a 
 new inverse. While discussed in terms of input-output analysis, it is 
 to be emphasized that the techniques developed here do not require the 
 assumptions of input-output analysis to be valid and are thus generally 
 applicable to any type of large-scale matrix system. 
 
II. PRELIMINARY REMARKS 
 
 An input-output model which represents a complete economic 
 system is referred to as a Leontief model and is a convenient way of 
 representing an interindustry transaction table is by a partitioned 
 
 Leontief matrix: 
 
 L = 
 
 w 
 
 CD 
 
 where y is a final demand column vector, Z is an intermediate product 
 
 flow matrix,w is a value added row vector, and L is the Leontief 
 
 p 
 matrix . Letting X denote a diagonal matrix of industry outputs, 
 
 we can obtain the technical coefficient matrix A by, 
 
 -1 
 
 A = ZX 
 
 (2) 
 
 The elements a. . of A show the direct purchases made by the 
 j industry from the i industry per dollar of output. Letting e 
 and I denote, respectively, a vector of l's and the identity matrix, 
 we have 
 
 -1 
 
 x = Ze + y = Ax + y = (I - A) y 
 
 i-l • 
 
 (3) 
 
 (I-A) " is the Leontief inverse matrix and the elements of 
 
 it indicate the output requirements generated directly and indirectly 
 
 from industry i by industry j per dollar's worth of output delivered 
 
 n 
 
 to final demand. The elements a. . > 0, and ) a. . < 1 with the strict 
 
 ij - J aj - 
 
 inequality holding for at least one column j; assuming that A is irredu- 
 
 —1 3 
 
 cible, the spectral radius of A, p(A) < 1 and (i-A) "" exists. 
 
 In input-output analysis we are often concerned with solving 
 
 the system of equations (i-A) x = y repeatedly for various changes in 
 
 the elements of A. This system of equations expresses gross output 
 
requirements as a function of final demand and the technological struc- 
 ture of the economy, and changes in the elements of A can come about for 
 a variety of reasons. The elements a. . are observations subject to 
 errors and are often revised after the original matrix has been inverted, 
 changes along a single row or column of A can indicate technological 
 change, and, further, it is often desirable to disaggregate a single 
 row or column of A to obtain additional industry detail. The methods 
 developed below permit these solutions to be obtained efficiently, 
 accurately, and inexpensively for the first time. Similar computational 
 procedures are discussed by Golub in statistical applications and by 
 Saunders and Lermit in linear programming . 
 
 In order to be able to apply the numerically stable algorithms 
 developed in the following sections, the original matrix inverse must be 
 computed in the following manner. Let us denote (I - A) by B. In 
 order to solve the system of equations 
 
 Bx = y (10 
 
 T 
 we construct an orthogonal matrix Q (Q Q = I) such that 
 
 QB = R (5) 
 
 in which R is upper triangular. One choice for Q is 
 
 Q = Q , Q ~ • • • Q (6) ■ 
 
 * n-1 ^n-2 *1 
 
 where the Q.'s are elementary Hermitian matrices (Householder's 
 
 transformations) , each of the form 
 
 Q. = I - o.u.u. (7) 
 
 i ill 
 
 with a. = 2/u. u.. Let the original matrix B be denoted by B, , then 
 ill 1 
 
 the reduction to the triangular form is determined by the recursive 
 relation B k+1 = (i - cyyi * ) B R k = 1, 2, . . . , n-1 (8) 
 
where B is upper triangular, and 
 
 \ = (0 > •••• "• \,k * s k- V» Vk' (9) 
 
 2 n 2 
 in which S = J ^., , " fc ^ ie s ig n 0:f> S i n (9) is chosen such that 
 
 i=k 
 
 l\,k 4 s kl ■ l\,kl + l s J 
 
 The elements b.. in the above expression are those of B . Therefore 
 ij k 
 
 from (U) we have, QBx = Qy or Rx = g and x is obtained by backward 
 substitution. If the inverse of B is desired we replace y by e. (the 
 i column of the identity matrix), i = 1, 2, ..., n, and the solu- 
 tions x. constitute the columns of (I - A) 
 
 2 2 
 In the triangularization of B, QB = R, — n multiplications 
 
 are required if Q is the product of (n-l) Householder's transformations, 
 and — n if Q is the product of plane rotations, (Givens reduction )• 
 Usually n ranges from 100 to 1+00 . This method of deriving the inverse 
 coefficients (Householder's reduction), requires twice as many multi- 
 plications as Gaussian elimination. Nevertheless, it is more numerically 
 stable and as we shall demonstrate, the savings made by never having to 
 recompute the inverse "from scratch" make this sacrifice of computational 
 efficiency well worthwhile. 
 
III. COLUMN MODIFICATIONS 
 
 Each column of the direct coefficients matrix A shows the 
 distribution of the inputs required by a specific industry, and the 
 situation often arises where we wish to calculate the total impact of 
 a change in this distribution. Changes in relative prices may encourage 
 substitution of certain inputs for others, technological change can, 
 have profound influence on the makeup of an industry's inputs, or the 
 shortage of a certain type of energy source or raw material may force 
 an industry to alter the composition of its inputs. Obviously, these 
 changes in the input structure will not alter the properties of the 
 original system, and B = (I - A) -will still be nonsingular. 
 
 Let 
 
 b = b + [o : g : oj 
 
 then from (2) we have 
 
 QB = R + [0 ! v ± .* 0] 
 
 .th 
 
 where w. = Qg. and QB will be upper triangular except for the i column, 
 Let P be a permutation given by, 
 
 P = 
 
 in which 
 
 J n-i+l 
 
 (10) 
 
therefore 
 
 QBP = 
 
 #— 
 
 *"" 
 
 B l 
 
 : c 
 
 
 
 H 
 
 Cii) 
 
 where R and H are upper triangular and upper Hessenberg matrices 
 of order (i-l) and (n-i+l) respectively. Let Z be an orthogonal 
 matrix such that 
 
 ZQBP = 
 
 
 
 = R 
 
 (12) 
 
 is upper triangular. An economical way of doing this is to choose 
 Z as 
 
 Z = Z . ... Z_. Z. (13) 
 
 n-1 l+l l 
 
 where each Z is an orthogonal matrix (plane rotation) given by 
 
 z k = 
 
 1 
 
 '1 
 
 c n s 
 k k 
 
 -s, c 
 
 k k 
 
 
 < row k 
 
 < row k+1 
 
 (iM 
 
 in which c, = cos a, , s n = sin a, , and the angles a, are chosen so 
 k k k k k 
 
 as to annihilate the element in the position (k, k+l). Let H = H 
 Then at the k step, 
 
 Vk-i- 2 ! QBP = 
 
 (15) 
 
 r (k+l) 
 
therefore, 
 
 -s *£>♦ %i S K J „ = o 
 
 k kk k k+l,k 
 
 ma ! k =to' c k = h S )/r k (i6> 
 
 i 
 
 where r = [h^ k + \. +1 k ]^ ^ which h. . belongs to H . Only rows 
 k and k+1 of H are affected, 
 
 (k+l) . Jk) x „ Jk) 
 
 *kj °k 
 
 hr = c * \j + S k\ + l,j 
 
 , (k+1) . (k) . „ , (k) , . 
 
 \+l,j " " s k h kj + c k h k + l,j (1T) 
 
 Denoting the orthogonal matrix ZQ by Q, we have 
 
 QBP = R (18) 
 
 The system Bx = y can be solved as follows, 
 
 (QBP) (P t x) = Qy ; 
 
 i.e. 
 
 Rq = y (19) 
 
 where y = Qy, solve for q by backward substitution then x = Pq. 
 
 Thus if B is a matrix in which only the i column is different 
 from that of B, then the number of multiplications required to solve the 
 system Bx = f are roughly, [|- n + 2(n-i) ] , i.e., a maximum of 
 only ~ n instead of — n if we were to solve the problem "from 
 scratch". Obviously, if i = n the problem is trivial. 
 
IV. ROW MODIFICATIONS 
 
 In interindustry analysis ve are usually more concerned with 
 the effects of changes in the elements in a row of the direct coeffi- 
 cients matrix than with modifications in the column elements. The row 
 distribution of the A matrix shows the sales of an industry's output to 
 all industries; this information has been applied to a variety of 
 situations. One of the more important of these is market analysis for 
 an industry, where input-output analysis is used to determine the effects 
 
 on an industry's sales of changes in economic conditions or changes in 
 activity within other industries. The analysis of the total effects 
 
 of changes in the distribution of an industry's output can be accomplished 
 in two stages: 
 
 (i) removing row b_. of B 
 Let, 
 
 B i = B - 
 
 (20) 
 
 then it can be easily shown that 
 
 t t t 
 
 B n B = B B - b. b. 
 
 11 11 
 
 from ( 5) we see that, 
 
 ^R = B t B 
 
 (21) 
 
 Since B B is a symmetric matrix then we can write 
 
 R^R n = R^ - b.b t 
 11 li 
 
 (22) 
 
 Let v be a column vector defined by R v = b., then from (22) we obtain 
 R^R X = R t (I - w* )R 
 Wow we can construct an orthogonal matrix Z such that Zv = ae , 
 
 thus 
 
 R^R X = rV (I - a^e*) ZR 
 
 (23) 
 
t 2 
 It can be easily shown that v v = a = 1, i.e., R is singular, as it 
 
 should be, and 
 
 R*R = rVd 2 ZR (21+) 
 
 in which D = diag (0, 1, ..., l). Hence 
 
 R = PDZR (25) 
 
 where P is an orthogonal matrix that reduces the matrix (DZR) to the 
 upper triangular form. The orthogonal matrix A can be constructed such 
 that ZR is not a full matrix but an upper Hessenberg one. This can be 
 done if we take 
 
 z = z 1 z 2 ... z n _ x (26) 
 
 where each Z is as given by (lU). The angles a are chosen as follows: 
 
 ■K K. 
 
 Let v = v (n ~ , and define v^ (k = 1, 2, ..., n-l) by 
 
 T (*-i) . v <k) (27) 
 
 (k) 
 
 where v is of the form 
 
 (k)* t (k) (k) (k) . .. 
 
 (lr_l ) (]r) 
 
 From (2?) we see that v. ; = v. for i = 1, 2, ..., k-1, and 
 (k-1) (k) (k) 
 
 \ - c k \ + s k Vi 
 (k-1) _ (k) (k) (OR , 
 
 v. ., = -s v + c. v. ._ (20). 
 
 k+1 k k k k+1 
 
 (k-l) 
 The angle n is determined such that v, . is annihilated, thus 
 
 k. k+1 ' 
 
 S k = \ + l /p ' c k = V k /p (29) 
 
 where p = [(v< k) ) 2 + (v^) 2 ]^ and 
 k k+1 
 
 (k-1) 
 \ = P (30) 
 
10 
 
 Thus, since ZR is an upper Hessenberg matrix and D = diag (0, 1, ..., l) 
 it is clear that P in (25) is a permutation matrix given "by 
 
 P = 
 
 n-1 
 
 (31) 
 
 and R is upper triangular with the last diagonal element being zero. 
 
 1 
 
 (ii) adding a new row d. 
 
 Let, 
 
 B 2 " B l + 
 
 (32) 
 
 therefore, 
 
 B 2 B 2 " B 1 B 1 + d i d l 
 
 Again since B B is symmetric we can write, 
 
 E 2 R 2 * R ! R 1 + d i d l 
 
 (33) 
 
 this equation is satisfied if Z is an orthogonal matrix of Order (n+l) 
 
 such that 
 
 «1 K 2 
 
 (34) 
 
 R] 
 
 
 
 We choose Z as, 
 
 Z = Z Z. . . . Z •■ Z 
 1 2 n-1 n 
 
 (35) 
 
 where the Z 's (k = 1, ..., n-l) are as given in (lk) and Z is the 
 K- n 
 
 permutation matrix 
 
 
 
 ' 1 
 
 I 
 
 n 
 
 
 
 , thus the matrix 
 
11 
 
 z 
 
 n 
 
 r r i "I f fi (—> 1 
 
 I ••'" ' I is of the form 
 
 L C L O(lxn) J 
 
 where H is an upper Hessenberg matrix. The angles cl of Z 
 
 (k = 1, 2, . .., n-1 ) are chosen such that H is reduced to an upper 
 
 triangular matrix R . 
 
 Thus if we wish to solve the system 
 
 B 2 x = y (37) 
 
 where B_ is same as the original matrix B except of the i row, we 
 premultiply both sides of (37) by B , 
 
 4 B 2 x = b\ y 
 
 (R^R 2 ) x = y (38) 
 
 * t t * 
 
 where y = B y. By forward substitution we obtain q in R. q = y, then 
 
 by backward substitution we solve for x in R^x = q. 
 
 Changing the i row of B and solving the new system B x = y 
 
 13 2 
 requires roughly — — n multiplications and 2(n-l) square roots, which 
 
 2 3 
 
 is again a substantial saving compared to — n multiplications. 
 
12 
 
 V. DISAGGREGATION 
 
 Disaggregation of the industry classification scheme — the 
 division of industry sectors into detailed industries — is one of the 
 most frequently discussed topics in input-output analysis. This 
 is important from a theoretical point of view where economists have 
 
 sought to determine "optimal "levels of disaggregation for input-output 
 
 7 
 tables, but it is especially significant from an empirical standpoint. 
 
 Individual firms and industries do not possess the resources to con- 
 struct their own interindustry tables and usually have to disaggregate 
 the rows and columns of the Commerce Department table in which they are 
 specifically interested. Even the government often disaggregates cer- 
 tain industries after the original interindustry study is- completed. 
 For example, after the 1958 U. S. study had been completed the Commerce 
 Department compiled additional transactions data on industries lU, 
 food and kindred products, 38, primary nonferrous metals manufacturing, 
 and 68, electric, gas, water and sanitary services, and disaggregated 
 
 o 
 
 these three industries into 15 more detailed industries. The 1958 
 
 direct coefficients matrix was thus expanded from 82 industries to 9^ 
 industries, but primarily for computational reasons a 9^-order inverse 
 matrix was never derived. The techniques developed here can be used to 
 compute an expanded inverse from the original inverse matrix and thus 
 avoid the effort of computing a new (i-A) inverse every time the trans- 
 action data are disaggregated. 
 
 Let us suppose that we wish to expand the i row and column 
 of the original matrix, of order n, into m rows and columns. If m > n 
 a new matrix B* will have to be formed and Householder's transformations 
 then used to reduce it to an upper triangular matrix as in (5). However, 
 
13 
 
 if m « n substantial computational savings may be obtained by proceed- 
 ing in the folio-wing manner. 
 
 Let B be partitioned as follows, 
 
 B = 
 
 B 
 
 11 
 (i*i) 
 
 21 
 
 B. 
 
 12 
 
 B, 
 
 22 
 
 (39) 
 
 and form the (m+n x m+n) matrix C as, 
 
 C = 
 
 " B ll '. 
 
 V 
 
 B 12 
 
 % : 
 
 ' ° 2 
 
 S 
 
 _ B 21 . 
 
 £ 
 
 : B 22 
 
 } 
 
 m 
 
 (Uo) 
 
 where the i row of C n and the i column of C, are zero. The rest 
 
 1 U 
 
 of the elements of C , ..., C constitute the m rows and columns to 
 replace the i row and column of B. Thus the rank of C > n+m-1 . 
 
 Let tt be a permutation matrix given by, 
 
 *1 = 
 
 m 
 
 n-i 
 
 (41) 
 
 Therefore C = tt C tt is given by, 
 
1U 
 
 c = 
 
 B ll 
 
 ■ \ s : 
 
 c i 
 
 B 21 
 
 : B 2 2 
 
 C 3 
 
 % 
 
 : s 
 
 : ° 2 , 
 
 B 
 
 
 
 E 2 
 
 E i . 
 
 
 (mxn) 
 
 ► — 
 
 (U2) 
 
 Define the (m+n x m+n) orthogonal matrix 1^ by. 
 
 T = 
 1 
 
 Q. 
 
 m 
 
 where Q is given by (2), thus 
 
 1 - 
 
 (U3) 
 
 ¥e can construct an orthogonal matrix T as a product of several 
 plane rotations (since m << n, otherwise we choose T as the product 
 of Householder's transformations) such that 
 
 T T 
 2 1 
 
 B 
 
 E 
 
 1 J 
 
 Hence, 
 
 TTC = 
 2 1 
 
 
 
 E„ 
 
 (UO 
 
 J h J 
 
 (1*5) 
 
15 
 
 where 
 
 L. 4 J 
 
 2 12 
 
 Now we can choose an orthogonal matrix T and a permutation ^ both 
 of order m such that TEi it is an upper triangular matrix Rp of 
 rank > m-1. Let 
 
 T = 
 3 
 
 "" 
 
 •" 
 
 I 
 
 n 
 
 
 
 o ; 
 
 T 
 
 .» 
 
 J 
 
 and 7T = 
 
 I 
 
 n 
 
 — 
 
 : o 
 
 
 
 ; j 
 
 therefore, 
 
 t~ 
 
 (T 3 T 2 T lT2 ) (^c, ) = 
 
 Rn 
 
 ! E 
 
 1 
 
 3 
 
 
 
 . R~ 
 
 
 2 
 
 „. 
 
 _ 
 
 = R 
 
 (k6) 
 
 Without loss of generality assume that ir = I. Postmultiplying hoth 
 sides "by a permutation P as given in (10) except n is replaced by m+n, then 
 (T T^P) (P^P) = RP 
 
 where the (m+n) row and column of B = P CP are the i th row and 
 
 column of C. Now RP is of the same form as the right-hand side of (ll), 
 
 we can then choose an ortnogonal matrix I, such that 
 
 (T^T T^P) (P^P) = R 
 
 0*7) 
 
16 
 
 is upper triangular. Writing (hj) as 
 
 TB = R 
 where T is orthogonal, then if we partition B and R as 
 
 B = 
 
 B 
 
 w 
 (lxm+n-l) 
 
 , R = 
 
 J lxm+n-l) 
 
 (W 
 
 removing the last column we obtain 
 
 * 
 
 B 
 
 
 R 
 
 t 
 w 
 
 
 
 
 L_ -i 
 
 
 L. «J 
 
 Therefore, 
 
 B B = R R - ww 
 
 Since R is of rank (m+n-l), then 
 B B = R (I - w ) R 
 
 *N~t 
 
 (U9) 
 
 (50) 
 
 where v = (R ) w, i.e. v is obtained by forward substitution in 
 R v = w. If V is an orthogonal matrix such that Vv = ge_ L we get 
 
 ** * t ** t , 2 t N * 
 
 B B = ITU = R V X (I - 3 e e x ) VR 
 
 (51) 
 
 where U is upper triangular. Since B B is a positive definite matrix 
 
 then g < 1 and 
 
 t *^ t~? * 
 
 U U = R V D VR 
 
 where D 2 = (l - g 2 , 1, . . . , 1 ) . 
 
 (52) 
 
 Similar to section III we construct V such that VR is an 
 
 upper Hessenberg matrix. Consequently we construct an orthogonal 
 
 matrix Z = Z . .. Z Z , where N = m+n-l, (similar to (26)), 
 
 *~ * 
 
 such that Z DVR is upper triangular; i.e. 
 
 U = Z DVR 
 
 (NxN) 
 
 (53) 
 
17 
 
 Returning to our original question which was to solve the system 
 
 B'x = (tt^ B tt 3 ) x = y (5^) 
 
 where y is now of dimension (m+n-l) and tt is a permutation given 
 by, 
 
 
 I. 
 
 i- 
 
 -1 
 
 
 
 
 
 "3 = 
 
 
 
 
 
 
 I 
 
 
 
 
 
 I 
 
 m 
 
 
 
 n-i 
 
 (55) 
 
 we have, 
 
 B (tt x) = (tt y) 
 
 *t i 
 
 (B B ) (tt x) = B tt 
 
 3^ ; 
 
 i.e. > 
 
 U Uq = y 
 
 (56) 
 
 By forward substitution we obtain q in U q = y, and by backsbustitu- 
 
 t 
 tion we obtain q in Uq = q. Finally, x = tt q. 
 
 Note that for all the previous modifications we need only 
 store Q and R, (QB = R). In addition, if we wish to only change rows, 
 we need not even store Q. If it is desired to disaggregate other 
 rows and columns these operations can be repeated for each disaggrega- 
 tion. 
 
 In expanding the i row and column of B into m rows and 
 
 columns and solving the resulting system of equations, the operations 
 
 2 13 
 
 involved are roughly (an + 8n + y) multiplications where a = — + 3m, 
 
 2 2 13 
 
 B = m (Urn + 13), Y = m (t m + ~ p") • Therefore if m << n the operations 
 
 are again of the order n 
 
18 
 
 VI. SUMMARY AND CONCLUSIONS 
 
 This paper has developed a method for determining the effects 
 on the Leontief inverse matrix of specified changes in the coefficients 
 of the direct requirements matrix which avoids the difficulty of recom- 
 puting the Leontief inverse. Once the original inverse matrix has been 
 computed according to the algorithm given in Section II, additional in- 
 verse matrices corresponding to new sets of interindustry relationships 
 can be computed accurately with savings in computation of order n, 
 where n is the order of the input-output matrix. The use of these methods 
 was demonstrated by considering three types of analyses very important in 
 interindustry work: changes in the distribution of the direct coefficients 
 down a single column, changes in the direct coefficients along a row of the 
 matrix, and the disaggregation of economic sectors into detailed industries. 
 These techniques can also be used to analyze the effects on the inverse ma- 
 trix of other similar types of perturbations in the direct requirements data. 
 
 The method suggested here for computing the original inverse 
 matrix requires roughly twice the time of an algorithm such as Gaussian 
 elimination. Thus, if the inverse matrix is to be computed only once and 
 no further analysis is anticipated, the techniques developed here will 
 be of little use. However, if repeated inverse matrices corresponding 
 to changes in technical coefficients are required, our methods can yield 
 substantial savings in time, effort, and computer costs with no sacrifice 
 in accuracy. 
 
 In relation to interindustry analysis the techniques developed 
 here can have important effects for both empirical work and theoretical 
 research. Empirically, these methods should be of great aid to the 
 input-output user community. As has been indicated, one of the major 
 
19 
 
 classes of users of interindustry data is the business community which 
 relies on input-output data for a wide variety of purposes such as product 
 planning and market analysis. The development of these computationally 
 efficient methods implies that, once the original inverse matrix is com- 
 puted by the method suggested here, individual corporations or commercial 
 associations can conduct almost any type of meaningful simulation analysis 
 they wish with a minimum investment of resources. Practical experiments 
 concerning input-output tables at even 500-order or 600-order levels of 
 detail are now entirely feasible for even relatively small businesses and 
 organizations. 
 
 The potential advances these methods make possible for basic 
 interindustry research are even more exciting. For four decades economists 
 have speculated on the types of experiments it would be desirable to con- 
 duct to obtain a better understanding of the input-output model: repeated 
 revisions of the technical coefficients to obtain different types of con- 
 sistent solutions, various types of sensitivity analyses to determine the 
 most critical sectors or coefficients, frequent incorporation of new data 
 as they come available into an existing interindustry structure to derive 
 
 more updated input-output tables, and other related types of large-scale 
 
 Q 
 
 empirical analyses. Until recently the computational facilities did 
 
 not exist which would permit this type of work with any realistically 
 detailed interindustry system. Even with the development of the required 
 computer hardware, however, the effort and costs involved in this type of 
 large-scale matrix simulation analysis has prohibited it from being even 
 attempted by all but the most generously funded research projects. The 
 techniques presented here will make a substantial contribution toward 
 reducing the complexity and costs of this type of work and thus make it 
 
20 
 
 feasible to a wide range of researchers. Thus, no longer must economists 
 be concerned with deriving "optimal" methods of aggregating input-output 
 data sets to manageable size or with attempting to determine theoretically 
 the total effects of different types of errors, changes, or patterns of 
 variation in the technical coefficients. 
 
 Leontief's classic work The Structure of the American Economy 
 was subtitled "An Empirical Application of Equilibrium Analysis". The 
 intelligent use of the methods developed in this paper can aid greatly 
 to our understanding of the detailed workings of an empirical equilibrium 
 system. 
 
21 
 
 Footnotes 
 
 The 1963 BEA input-output matrix in 367 industry detail is given 
 in [ll]; the 19^3 matrix in ^78 industry detail has not been 
 published. 
 
 2 
 
 The appears in the lower right hand corner of the Leontief 
 
 matrix because all nonproduction accounts of the system are 
 
 assumed to be consolidated. 
 
 •3 
 
 A proof of this is given in Ortega [7]. 
 
 See Golub [5], Saunders [8], and Lermit [6] 
 
 See Wilkinson [lO]. 
 
 /- 
 
 For a discussion of the marketing uses of input-output data see 
 Evans [ 3 ] . 
 
 T See Ghosh [1+] and Stone [9], Chapter 8. 
 
 o 
 
 The additional 1958 transaction data for these industries are 
 given in [l]. 
 
 For an interesting discussion of these issues see Arnold [2]. 
 
22 
 
 References 
 
 [l] "Additional Industry Detail for the 1958 Input-Output Study", 
 Survey of Current Business , April 1966, pp. lU-17. 
 
 [2] Arnold, Robert K. "input-Output Projections and Sensitivity 
 Analysis", Paper presented at Business Applications of Input- 
 Output Analysis: A Symposium of the Institute for Interindustry 
 Data, New York City, December 7, 1967. 
 
 [3] Evans, W. Duane "Marketing Uses of Input-Output Data" Journal 
 of Marketing , XVII, No. 1, pp. 11-21 (July 1952). 
 
 [h] Ghosh, A. "Input-Output Analysis with Substantially Independent 
 Groups of Industries", Econometrica , Vol. 28, No. 1, I960, 
 pp. 88-96. 
 
 [5] Golub, A. "Numerical Computations for Univariate Linear Models", 
 Technical Report No. STAN-CS-236-71 , Computer Science Department, 
 Stanford University, 1971- 
 
 [6] Lermit, J. "A Linear Programming Implementation", CAC Document 
 No. k6, Center for Advanced Computation, University of Illinois 
 at Urbana-Champaign, 1972. 
 
 [7] Ortega, James Numerical Analysis: A second course , Academic 
 Press, 1972. 
 
 [8] Saunders, M. A. "Large-scale Linear Programming using the Cholesky 
 Factorization", Technical Report No. STAN-CS-72-252, Computer 
 Science Department, Stanford University, 1972. 
 
 [9] Stone, Richard Input-Output and National Accounts . Paris: 
 Organization for European Economic Cooperation, I960. 
 
 [10] Wilkinson, J. H. The Algebraic Eigenvalue Problem , Oxford, 
 1965. 
 
 [ll] U. S. Department of Commerce, Bureau of Economic Analysis. Input - 
 Output Structure of the U. S. Economy: 1963 (three volumes ) . 
 Washington, D. C: U. S. Government Printing Office, 1969. 
 
UNCLASSIFIED 
 
 Security ClBSBiflcation 
 
 DOCUMENT CONTROL DATA R&D 
 
 (Security clmaa I licit Ion ol tltla. 
 
 InalmmtnM mmtolmtlam muat ba antata4 wham tha orarall rgggrj la etaaalflad) 
 
 ■ ORIGINATING ACTIVITY (Carpnrali author) 
 
 Center for Advanced Computation 
 University of Illinois at Urbana- Champaign 
 Urbana, Illinois 61801 
 
 *». REPORT SECURITY CLASSIFICATION 
 
 UNCLASSIFIED 
 
 26. GROUP 
 
 J. REPORT TITLC 
 
 Methods for Increasing the Computational Efficiency of Input-Output and Related 
 Large Scale Matrix Operations 
 
 4. descriptive NOTIl (Typa •/ ramntt «W Htelualwa 4mtmm) 
 
 Research Report 
 
 B AUTHOR(S) (Flrat mum, mtJdJt Initial, Imal nama) 
 
 Ahmed A. Sameh and Roger H. Bezdek 
 
 • ■ NIRORT DATE 
 
 February 1973 
 
 7«. TOTAL NO. OF PACE* 
 
 28 
 
 76. NO. OF REFI 
 
 11 
 
 %a. CONTRACT OR GRANT NO. 
 
 DAHCO^f 72-C-OOOl 
 
 b. PROJECT NO. 
 
 ARPA Order No. 1899 
 
 •a. ORIGINATOR'S REPORT NUMICRUI 
 
 CAC Document No. 66 
 
 OTHER REPORT NO(S) (Any othat number* that may ba aaalgnad 
 thla rmpori) 
 
 10. DISTRIBUTION STATEMENT 
 
 Copies may be requested from the address given in (l) above. 
 
 II. SUPPLEMENTARY NOTES 
 
 12. SPONSORING MILITARY ACTIVITY 
 
 U. S. Army Research Office-Durham 
 Duke Station, Durham, North Carolina 
 
 IS. ABSTRACT 
 
 This paper develops numerical methods for greatly increasing the 
 computational efficiency of input-output and related large scale matrix 
 operations. Once the Leontief inverse matrix is computed according to 
 the algorithm specified here, these methods permit the accurate determination 
 of the effects on the inverse coefficients of changes in the transaction 
 data with far fewer operations than required to compute the inverse "from 
 scratch. " These techniques are demonstrated by considering modifications down 
 a column of the direct coefficients matrix, modifications along a row of the 
 direct coefficients matrix, and disaggregation of the industries in the new 
 system. The very large gains in efficiency of this method are indicated 
 and the implications of these techniques for empirical and theoretical 
 input-output research are briefly discussed. 
 
 DD F - , r..1473 
 
 IMCLASSTFTF.n 
 Security Clasaificati 
 
 tion 
 
UNCLASSIFIED 
 
 Security Classification 
 
 KEY WORD* 
 
 Input -Output Matrix 
 Plane Rotations 
 Householder's Transformations 
 Linear Equations 
 
 HOLS. I *T 
 
 W 
 
 HOLI «T 
 
 UNCLASSIFIED 
 
 Security Classification 
 
mi