Three-dimensional simulations of metallization wires of VLSI/ULSI interconnections that are plagued with unreasonably large memory requirements and execution times are discussed. A strategy is presented for overcoming these problems. A principal feature is the use of a domain contraction technique, which accounts for the fringing electric field throughout the infinite domain above and below the levels where the wires appear and provides a major reduction in the number of nodal points for a finite-difference computation. Moreover, an iterative method (successive over-relaxation) is used to alleviate memory requirements, a nonuniformly distributed nodal array is used to reduce the number of nodal points still further, and parallel processing is used to reduce execution time. It is argued that rounded edges and corners for the simulation of the wires are the only appropriate configurations at current levels of miniaturization. This avoids the problem of electric-field singularities at sharp edges and corners and results in significantly reduced capacitance coefficients.>

An algorithm for computing the Chebyshev solution of a system of inconsistent linear equations is given. The algorithm, which is similar to the Revised Simplex method of linear programming, is a consequence of a reformulation of the ascent algorithm and the use of generalised inverses.

Some methods of successive approximation for the solution of simultaneous linear equations are discussed. The coefficient matrix A of the linear system is assumed to be sparse. It is shown that savings in the computer storage and the computing time are possible, if there exists a subset of the rows (columns) of A, consisting of only orthogonal rows (columns). Such savings are also possible, if for some permutation matrices P and Q, PAQ has a particular structure, viz., singly bordered block diagonal form. It is shown that the set of orthogonal rows (columns) of A, as well as P and Q can be determined by using some results from graph theory (e.g., incidence matrices, row and column graphs, points of attachment). Geometrical interpretations of the methods and their inter-relatiohip are given.

An algorithm is given for minimising the number of non-zero elements created during the forward course of the Crout reduction (no new elements are created in the back substitution). Practical computational techniques for the efficient utilisation of the algorithm are also discussed.

An iterative method for the solution of a system of simultaneous linear equations, having a singular coefficient matrix A, is described. The method is obtained by minimizing (in the least squares sense) the image under AT of a given residual vector.

A method for computing the generalized inverse of a matrix is described, which makes use of the well-known Gauss–Jordan elimination method and the orthogonal triangularizations.

The problem of transforming a given sparse matrix A into a block diagonal form (b.d.f.) and the subsequent transformation of each of the block diagonal matrices into as nearly upper triangular form (u.t.f.) as possible, by using only row and column permutations, is discussed. It is shown how some of the results from Graph Theory can be used to transform A to the b.d.f. In order to transform the block diagonal matrices into the u.t.f.'s, two methods are described, one of which makes use of linear programming while the other uses approximate probabilistic arguments. The latter method, in relation to the computational effort, yields significant results in practice.