Engineering with Computers 4, 197-203 (1988)

c,an

Br,s

9 Springer-Vedag New York Inc. 1988

A LISP-Based Object-Oriented Approach to Structural Analysis G.R. Miller Department of Civil Engineering, University of Washington FX-10, Seattle, Washington

Abstract. An approach to structural analysis is presented in which object-oriented data structures make it possible to arrange computational tasks in a unique fashion. A general matrix-free solution algorithm for use with arbitrary assemblages of finearly connected objects is presented, followed by an overview of a prototype structural analysis program built entirely on such an object-oriented data structure. The principal result is due to the flexibility inherent in this type of data structure, which makes it possible to analyze structural models incrementally as they are developed. Although certainly useful in traditional contexts, the parallel nature of the scheme could be particularly powerful in a multiprocessor environment.

1

Introduction

Historically, computer-aided structural analysis has been developed in and optimized for a FORTRANbased computing environment. This has led to the existing computational paradigm consisting of three essentially distinct steps: preprocessing, followed by number crunching, followed by postprocessing. Although significant development has occurred over the years in terms of enhancements to each of these steps, the overall procedure has remained largely unchanged. The computer world has changed drastically, however, and it would seem worthwhile to begin to reexamine the fundamental ways in which engineering computation is done in light of present and developing systems [1]. This paper presents the results of some exploratory research considering the development of an alternative approach to computational mechanics using a comtemporary LISP computing environment (Symbolics Common LISP running on a Symbolics 3640 [2]), generally associated with artificial intelligence or expert systems. Rather than merely attaching a high-level interface onto a traditional analysis package as a facade, a prototype pro-

Reprint requests: G. R. Miller, Department of Civil Engineering, University of Washington, FX-10, Seattle, WA 98195, USA.

gram has been developed from scratch using an object-oriented, incremental computation approach. The primary feature of this approach is the use of object-oriented data structures [3-5], which allows the basic building blocks of the program to correspond to the physical objects being modeled. Thus a given structure, which is implemented as an object itself, is composed of a hierarchy of component objects: structural-element objects (beam and truss elements, e.g.), connecting joint or node objects, which contain among their properties degrees of freedom, which are also implemented as objects. As usual in object-oriented programs, the information relevant to each object is known to itself directly, and it is further possible to build up complex objects using simple elements. The form of the program follows its function of modeling structural components, and this leads naturally to intuitive interfaces: what appears on the screen as a representation of an object in a sense is that object, and accessing the representation (e.g., pointing at it with a mouse) accesses the object itself. The real impact of the object-oriented approach, however, is in its ability to allow a complete integration of the input/output and analysis computational tasks. Thus a model can be incrementally analyzed as it is developed. This ability to allow analysis to proceed in parallel with model definition process could be quite useful in present-day applications such as design and optimization, but could have an even greater impact in a parallel processing environment. The paper is written in two parts. In the first part a general solution algorithm is presented for use with linear systems modeled by object-oriented data structures. It is shown how this type of approach enables what is equivalent to incremental matrix inversion, making it possible to perform solutiontype calculations in parallel with input and interface operations. The second part describes the specifics of using object-oriented data structures in the context of structural analysis. Beyond the ability to rapidly construct powerful and intuitive programs, the notion of incremental computation is extended

198

G.R. Miller

b

(

a

c

Fig. 1. A typical network model of a linear system

further resulting in a completely integrated input/ analysis/output package for use in structural analysis and design.

2 An Object-Oriented Solution Algorithm In this section a matrix-free solution algorithm is developed to compute the equivalent of the inverse matrix for an arbitrary assemblage of linearly connected objects (it is assumed in the following discussion that the interactions are symmetric; this assumption could be modified if necessary). Consider such an assemblage as depicted in the network representation of Fig. 1. Here the connection between each object is quantified by an influence coefficient, and the typical mathematical description for the assemblage would be a matrix containing these coefficients:

[i g0bg0c il The shortcomings of this type of description are twofold: (1) its inability to represent efficiently networks with sparse or highly banded structures and (2) the need for an artificially imposed indicial reference system that is highly structured. The first of these shortcomings may be dealth with through clever programming, although typically at the expense of the second shortcoming. The difficulty with a highly structured data format is that it requires highly structured input, which is not well suited for situations such as design where frequent and ongoing modifications are continually being made to the system being analyzed. This difficulty is typically handled through preprocessing software, but by necessity this separates the computa-

tional task into rather large, distinct parts that can only be linked in an end-to-end manner: the analysis cannot begin until the preprocessing is finished. As will be seen later, given the flexibility to do so, there is much to be gained by enabling the analysis to proceed in parallel with interface processing. As an alternative to the matrix-based description, an object-oriented description can be developed to provide an inherently efficient representation along with a high degree of flexibility. Consider such a description for the network of Fig. 1. To build an object-oriented description, each node is defined as an object, each of which " k n o w s " the other objects (i.e., nodes) to which it is connected and the magnitude of that connection. Thus in a LISP context the network can be represented by a global list of nodal objects:

Objectl: Object2: Object3: Object4:

((Objectl ((Object2 ((Object3 ((Object4

9 a) (Object3 9f)(Object4 9 h)) 9 b) (Object3 9 g)) 9 c) ) 9 d) )

This type of representation is automatically as sparse and banded as the network or system being modeled, since only actual connections are stored, resulting in no unneeded zeros. This representation is also extremely flexibile, since there is no requirement in general for the ordering in any of the lists to follow an externally imposed structure (e.g., the influence list for object2 could just as easily be in reverse order). In general, this flexibility allows one to work with less structured or even partially incomplete, evolving input data structures, such as naturally arise in design contexts. From a merely bookkeeping point of view this can allow for addition and deletion of objects and connections from the network assemblage without the need for indicial updating and modification or concern about bandedness in the stored representation. Beyond this, as will be seen subsequently from a computational point of view, calculations can be run in parallel with the input tasks on several useful levels. Despite the inherently loose format of this representation, for some applications it may be desirable to impose varying degrees of structure through the inclusion of ordering requirements. In the preceding illustration, for example, it has been assumed that once the objects are placed in the global object list, their relative positions will not change, This particular imposed ordering removes the need to store interactions that are redundant due to symmetry (e.g., it is not necessary to include (Objectl 9 f) in the influence list of Object3). If desired, this imposi-

A LISP-Based Object-Oriented Approach to Structural Analysis

tion of varying levels of structure could be extended all the way up to achieving a standard condensedstorage matrix representation, although clearly with a corresponding loss in flexibility. Given any model of a linear system, the normal goal is to be able to specify arbitrary inputs and to calculate the corresponding output values. In the present context it is natural to associate input and output values with the corresponding object (or node in the context of Fig. 1, or degree of freedom in the context of structural analysis, etc.). The problem is to be able to take given input values and compute the corresponding output values using the object-oriented data representation. To calculate an inverse from this type of representation, one needs to perform similar calculations as in matrix inversion without the aid of an indicial structure. To accomplish this, a set of LISP functions have been developed that essentially perform a Choleski decomposition directly from an object list as described earlier and store the result back into a similar data structure. The Choleski decomposition procedure is well known and consists of replacing the linear system AX = B with an equivalent system of the form RRa~X = B, in which R is a triangular matrix. The components r,7 of R can be determined from the components a U of A using the following (see e.g., Ref. [6]):

rJi

= -rii

aij - - ~ rik rjk k= 1

forj > i

(1)

The computations for the r,j using this relation typically proceed in a recursive row-by-row fashion, with the construction of each row depending on the results of the previous row. To adapt this procedure for use with lists of objects and interaction lists, it is helpful to replace the preceding indicial equation with an equivalent object-oriented description. To this end we define Rlists: additional lists of information analogous to the influence lists defined earlier, except that r0-type information will be stored rather than the au's of the influence lists. An equivalent, albeit verbose, analogue to Eq. (1) is thus The R value in the object-j slot of the R-list of object-i = [(The A value in the object-j slot of the influence list of object-i) - ~ (the R values in the R-list of object-i) * (The R values in the R-list of object-j)]/(The R value in the object-i slot of the R-list of object-i) This statement is relatively simple to translate into LISP code [7,8]:

199

(let ((R-value ((/(- (get-value object-j object-i) (sum-prod (object-R-list object-j) (object-R-list object-j))) (get-value object-i object-i))) (setf (object-R-list object-i) (acons object-j R value (object-R-list object-i)))) in which the functions object-R-list and get-value are accessors returning the R-list of a given object and the influence coefficient between two given objects, respectively. The function sum-prod is a simple recursive function that returns the value of the sum of the products of the values of two association lists: (defun sum-prod (list-1 list-2) (if list- 1 (+ (* (cdar list-l) (cond ((cdr (assoc (car (car list-l)) list-2))) (t 0))) (sum-prod (cdr list-l) list-2)) 0)) Once these fragments of code have been constructed to calculate individual R-values, it is relatively simple to add the additional surrounding code needed to compute all the R-values. Having the Rvalues, one can calculate the actual solution to a given problem by using an object-oriented analogue for forward-backward substitution. An example of the necessary code is given in the appendix for both these tasks. Essentially, the surrounding code given replicates the row-by-row construction procedure typically associated with Choleski decomposition, except that the construction takes place object by object. Due to the flexibility of the data structure, this object-by-object calculation could also be performed incrementally. Thus once an object has had all its connections made, its R-values could be calculated immediately, provided the R-values had been calculated previously for each of the other objects preceding it in the global object list. In practice, this can be accomplished by partitioning the global object list into two parts: a list of "used" objects and a list of unused objects. When an object has all its connections made, it is placed at the end of the " u s e d " list, and the inversion calculations are performed. This procedure has similarities to frontal solution methods [9], with " u s e d " objects corresponding to eliminated variables and the wave front information contained in the variable "bandlist" (see code in the Appendix). Although little problem exists with disk reads and writes if the solution is proceeding incrementall3/, it should be noted that there is a definite tradeoff in memory efficiency associated with this ap-

200

G,R. Miller

proach. First, regardless of the manner in which the R-values are obtained, for efficient forward-backward substitution it is necessary to store redundant R-transpose coefficients. Second, allowing the reordering of the global list as described earlier would require the storage of redundant influence coefficients (i.e., symmetry could not be exploited fully, since each object would be required to have a full influence list). These shortcomings are both related to the fact that extracting data from simple lists arbitrarily is a relatively slow process. By replacing the R-lists with a global array, one can remove the need to store R-transpose values for forward-backward substituion, although at the cost of losing the direct connection between an object and its data. For very large systems it would be possible to use substructuring, which could be implemented nicely in object-oriented fashion. There is no shortage of techniques for solving sets of linear equations, and the method presented here is by no means optimum in the traditional sense. The method does introduce different standards of optimality, however, for use in an object-oriented environment. The goals here are to keep as tight a correlation as possible between an object and its data, to allow as much calculation as possible using only information locally available to an object, and to allow calculations to occur incrementally as objects are created and connected.

3

An Object-Oriented Structural Model

In this section a hierarchical object-oriented data structure for use in structural analysis is presented along with a brief description of a program implementing these structures. The presentation uses the terminology and constructs appropriate to the Common LISP extension called "Flavors" [7,10], but the concepts could be applied equally well to any other object-oriented data type endowed with similar attributes. The overall concept is to view a structure as an assemblage of different types of objects, both physical and mathematical in nature; to define each type of object (flavor) along with its properties (instance variables); and then to construct the necessary software in effect to "teach" each type of object how to behave. The fundamental object type in structural analysis is the degree of freedom (DOF). In fact, from an analytical point of view a structure can be viewed essentially as an assemblage of linearly related DOFs that could be represented easily by a network of the form of Fig. 1. From the first part of this

paper it follows immediately that the attributes (henceforth referred to as instance variables) a degree of freedom must have to use the object-oriented solution algorithm are as follows: 1. 2. 3. 4.

Input value(s) (i.e., applied forces or moments) Output value(s) (displacements or rotations) Influence list (stiffness coefficients) R-list and RT-list (for storing the Choleski decomposition)

Again, it is simple to translate this into LISP-code: (defflavor DOF (input output influence-list R-list RT-list) 0 :initable-instance-variables :readable-instance-variables :writable-instance-variables) in which defflavor is a special form for defining flavors, and the final three arguments are keywords that render the instance variables readable, writable, and initializable. Note that this statement does not create any objects; it merely creates a type of object (thus the name flavor), which may be viewed as a template for creating and manipulating actual objects. The creation of an actual object of a given type (an instance of a flavor) involves an additional function, make-instance [7]. Although it would be possible to construct directly a structural model using DOFs alone, it is preferable to imbed the DOFs in a hierarchical framework of higher-order objects. Thus the next fundamental building block to define is the node or joint. A joint has both geometric and structural attributes associated with it. For simplicity consider the two-dimensional (2D) case and the following attributes: 1. Location (x-position and y-position) 2. Constraint (x-constraint, y-constraint, and rotation-constraint) 3. Degrees of freedom (u v 0) At a first glance it may appear that displacements and applied forces have been neglected in the nodal attribute list, but his information is associated with the DOFs one step down the hierarchy. The degreeof-freedom slots, u, v, and O, do not contain values, they contain DOFs. Thus the u-displacement of a given joint is simply the value in the output slot of the particular DOF that is in the u slot of the given joint. The following LISP code would return the udisplacement for any joint x: (DOF-output Ooint-u x)) in which joint-u and DOF-output are accessor functions created automatically when the flavors DOF

A LISP-Based Object-OrientedApproach to Structural Analysis

and joint are defined. DOF-output returns the value in the output slot of the given DOF, whereas joint-u returns the DOF in the u slot of the given joint. The next set of objects in the hierarchy are the actual structural elements themselves. As in the case of joints, structural elements possess attributes at several levels: geometric, physical, and structural. Furthermore, structural elements share many features, a fact that can be exploited using inheritance. For example, structural line elements all have the same basic geometric structure: that of a line. It is therefore possible to define a line flavor containing all the geometric propeties necessary to specify a line and to develop a corresponding set of functions and tools for tasks such as drawing and moving these line objects. It is then possible to include the line flavor as a component of a particular structural element, such as a 2d-truss element, enabling the structural element to inherit all the features of a line. Furthermore, the functions and tools designed to operate all lines will also operate on the structural elements. Thus the inheritance involves both features and functions. This is quite handy in developing interfaces, since structural and graphical information can be inherently blended. It is also useful for the development of the structural elements themselves. For example, once a 2d-truss element has been defined, its attributes and functions may then be inherited by other types of elements higher up the hierarchy. Consider a 2d-truss element flavor with the following attributes: 1. 2. 3. 4.

Material properties (Young's Modulus, E) Cross-section properties (area, A) Load (internal force) Connectivity information (end joints, joint-i and joint-j) 5. Structural properties (stiffness coefficients, AE/L) Then to develop a beam element, it merely would be necessary to include the additional properties required to define a beam (such as moment of inertia, additional stiffness coefficients, etc.) beyond those listed previously; all the shared attributes could be obtained directly through inheritance. Note further in the case of the 2d-truss element that some of the attributes (e.g., E and A) are input in nature, others (e.g., internal force) are output in nature, while still others (stiffness coefficients) are intermediate between input and output. Since all of this information is always available to a given element, one can organize the computations such that information is updated or computed as soon as it is

201

possible to do so. Consider, for example, the computation of global stiffness coefficients. Since these coefficients depend only on the material and crosssectional properties and the orientation of the member, they can be calculated as soon as these quantities are known. Furthermore, as soon as the stiffness coefficients are calculated, this information can be passed along to the connected joints, which may then update their DOFs' influence lists. This is equivalent to computing and assembling element stiffness matrices in parallel with the creation of the elements. Again, due to the object-oriented data structure, this may all be done independently of the rest of the structure. As the various DOFs influence lists are completed, they may be put into a global object list as discussed in the first part of this paper. As previously indicated, as the global object list grows the decomposition process can be carried out incrementally. Thus both assembly and partial solution can proceed along with the element definition and connection procedure. The result of this is that the normal major computation required at the completion of the input process is greatly reduced, since the final solution computation will involve only the forward-backward substitution. A prototype program has been developed incorporating many of the features described earlier. As is typical of LISP programs, the code consists of a large number of relatively short, simple functions. These functions are generally loosely connected, the actual connections largely being defined by the user. The program has a very clear structure, however, and that structure reflects its object-oriented base. Thus the code falls naturally into two main categories: object definition and object manipulation. The basic concepts of object definition can be surmised from the earlier discussion. Object manipulation involves "teaching" an object to do a task and then writing surrounding code to delegate tasks to the appropriate objects. As a simple example of this, consider the task of computing the axial force in a 2d-truss member. The following method (a method is a function that operates on objects) teaches this task to a single member: (defmethod (axial-force 2d-truss-element) 0 (let* ((dx ( - (DOF-output (joint-u joint-j)) (DOFoutput (joint-u joint-i)))) (dy ( - (DOF-output (joint-v joint-j)) (DOFoutput (joint-v joint-i)))) (cos ( / ( - xj xi) length)) (sin ( / ( - yj yi) length))) (serf Load (* AE/L (+ (* cos dx) (* xin dy))))))

202

The flavor being operated on is a "2d-truss-element," each instance of which knows its own end point (xi, yi, xj, and yj), end joints (joint-i and jointj), and physical parameters (A, E, length). Calculating the forces for all the members is then extremely simple: one needs only to tell each member to calculate its own force, which is accomplished in the following: (defun Compute-all-forces (element-list) (mapc #'Axial-Force element-list)) where the elements are contained in an element list, which could be viewed as defining a truss structure. Similar constructs are used throughout the program. The object-oriented structure is also apparent to the user. Objects and tasks presented on the screen are directly accessible by pointing and clicking with a mouse. Thus any information or process concerning the member is quickly and intuitively accessible. Also, the calculation turnaround time is extremely fast since very few large calculations are performed. The net effect is that the user has the perception of working quite directly with the structure being modeled. To a large degree many of these features can be implemented using appropriate preand postprocessing software in consort with traditional or more recent procedural languages such as FORTRAN or C. In the present approach, however, these features are incorporated naturally, with very little software overhead, and in a very flexible fashion. Furthermore, the blending of incremental computation and object-oriented, matrix-free data structures can be accomplished quite efficiently in a LISP environment, both in terms of execution and in the ease of software development. For many applications this type of program could provide a desirable alternative to present day systems.

G.R. Miller

derway to extend the program accordingly. It is not difficult to picture the further possibilities in a multiple processor environment. Here element generation could be assigned to one processor, element stiffness, and assembly processes could be assigned to another (which could follow close on the heels of the first), while still another could be assigned the task of incremental decomposition. This could provide a particularly powerful tool once multiprocessor machines become more widely available.

Acknowledgments This material is based on work supported by the National Science Foundation under Grant No. MSM-8657628, and by SymbolJes, Inc., Cambridge, Massachusetts.

References 1. Bishop P. (1986) Fifth Generation Computers. New York: Wiley 2. Moon, D.A. (1987) Symbolics architecture. Computer 20, 43-52 3. Booth, G. (1986) Object-oriented development. IEEE Softw. 12, 211-221 4. Stefik, M.; Bobrow, D. (1986) Object-oriented programming: Themes and variations. AI Magazine, 6, 40-62 5. Yonezawa, A., Tokoro, M. (Eds.) (1987) Object-Oriented Concurrent Programming. Cambridge, MA: MIT Press 6. Gastinel N. (1970) Linear Numerical Analysis. New York: Academic Press 7. (1987) Symbolics Common List--Language Concepts. Cambridge, MA: Symbolics, Inc. 8. Steele, G.L. (1984) Common LISP--The Language. Minneapolis, MN: Digital Press 9. Irons, B.M. (1970) A frontal solution program for finite element analysis. Int. J. Numer. Meth. Eng. 2, 5-32 10. Cannon, H.I. (1980) Flavors. Technical Report, MIT Artificial Intelligence Lab., Cambridge, MA

4 Conclusion This paper has presented an alternative approach for developing structural analysis and design programs. It has been shown how a different style of program can be constructed that allows computations to proceed in an incremental fashion. At the core of the approach is the use of object-oriented data and program structures. Although the paper has been couched in terms of structural analysis, it is clearly simple to extend the concepts into the full realm of finite element methods, and efforts are un-

Appendix The following code computes a Choleski decomposition for an object-oriented data structure. LISP code is notoriously difficult to read and frequently dialect-dependentmthe primary purpose of presenting this code is to give a basic impression of its compactness and its fundamental differences from analogous software developed using procedural languages.

Object Definition

(defflavor DOF ((input 0) output (influence-list '0) (R-list '0) (RT-list '0) ) 0 :initable-instance-variables :readable-instance-variables :writable-instance-variables) D e c o m p o s i t i o n Functions

(defun Compute-R-decomp (obj-list band-list) (if obj-list (let* ((o-n (car o-list)) (Rnn (sqrt ( - (get-vals o-n o-n) (sum-sqrs (object-R-list o-n)))))) (setq band-list (remove o-n (union band-list (mapcar #'car (object-influence-list o-n))))) (mapc #'(lambda (x) (let ((R-value ((/(- (get-value o-n x) (sum-prod (object-R-list o-n) (object-R-list x))) Rnn))) (serf (object-R-list x) (acons o-n R-value (object-R-list x)) (object-RT-list o-n) (acons x R-value (object RT-list o-n))))) band-list) (serf object-R-list o-n) (acons o-n Rnn (object-R-list o-n))) (Compute-R-decomp (cdr obj-list) band-list)) "finished")) (defmethod (get-value object) (object-j) (let ((chk (assoc object-j influence-list))) (if chk (cdr chk) 0)))

;Returns the influence coefficient ; between two objects

(defun sum-sqrs (list) (if list (+ (expt (cdr (car list)) 2) (sum-sqrs (cdr list))) 0))

;Returns the sum of the squares ; of the coefficients in an ; association list

(defun sum-prod (list-1 list-2) ;Returns the sum of the products (if list-1 ; of the coefficients in two (+ (* (cdar list-l) ; association list (cond ((cdr (assoc (caar list-l) list-2))) (t 0))) (sum-prod (cdr list-l) list-2)) 0)) Soloing Functions

(defun Solve (obj-list) (mapc #'RYB-solution obj-list) (mapc #'RTXY-solution (reverse obj-list)))

"forward substitution ;backward substitution

(defmethod (RYB-solution object) 0 (let ((R-serf (assoc serf R-list))) (serf output ( / ( - input (sum-prod-2 (remove R-self R-list))) (cdr R-self))))) (defmethod (RTXY-solution object) 0 (let ((R-serf (assoc self R-list))) (serf output ( / ( - output (sum-prod-2 RT-list)) (cdr R-self))))) (defun sum-prod-2 (list) ;similar to sum-prod (if list (let ((lead-list (car list))) (+ (* (cdr lead-list) (object-output (car lead-list))) (sum-prod-2 (cdr list)))) 0))