I would like to express my thanks to:
 - Richard Petti and Jeffrey P. Golden of Macsyma, Inc. (USA) for their interest in this work,
   for supplying Macsyma licenses and the modifcation of the LINSOLVE function,
 - The Center for Microelectronics of the University of Kaiserslautern, in particular
   Dr. Peter Conradi and Uwe Wassenmüller, for the support of the project,
 - Clemens, Frank and Michael for the first-class WG life and particularly Michael for the
   temporary hiring of its computer,
 - My parents and grandparents for their constant support during my study,
 - and quite particularly my friend Dr. Ralf Sommer for outstanding co-operation and the
   common enterprises of the last three years.

 Eckhard Hennig
 Braunschweig, August 1994
 

Summary:
Technical sizing functions require frequently the solution of sets of equations, which describe an object mathematically, after the values of the function defining element parameters. For the analytic solution of smaller sizing problems the application of commercial computer algebra systems offers itself such as Macsyma [ MAC 94 ], which is able, to manipulate and resolve after their variables symbolically extensive equations algebraically.
Despite their high efficiency these systems are however usually already overtaxed, if linear or weakly nonlinear, parameterized sets of equations are to solve after only one subset of their variables or be before-processed at least symbolically. In order to be able to treat such typically with design functions developing set of equations, in the context of this work, a universal symbolic equation solver based on heuristic algorithms was developed and implemented in Macsyma. Program module SOLVER extends the functionality of the Macsyma instruction SOLVE and LINSOLVE for the symbolic solution of algebraic equations or linear sets of equations by the ability for the selective solution of nonlinear, parameterized systems with degrees of freedom.
The first section of the available work describes some ranges of application of symbolic sizing methods, the request following from them to a symbolic equation solver as well as the used heuristic algorithms for the extraction of linear equations and for the complexity evaluation of algebraic functions. The second section contains an overview of the structure the Solvers and a guidance to its use. In the appendix is the source text of the module implemented in the internal higher programming language of Macsyma SOLVER.mac.

Table of contents
1 heuristic algorithms~1
1.1 introduction~1
1.1.1 numeric procedures in the comparison with symbolic methods~1
1.1.2 examples of areas of application of symbolic sizing methods~2
1.2 conventional equation solver~7
1.3 requirements of a symbolic equation solver~8.
1.4 extraction and solution of linear equations~10
1.4.1 intuitive methodologies for the search of linear equations~10
1.4.2 a heuristic algorithm for the search of linear equations~11
1.4.3 solution of the linear equations~13.
1.5 evaluation strategies for the solution of nonlinear equations~14
1.5.1 substitution systems for nonlinear sets of equations~14
1.5.2 heuristic procedures for the complexity evaluation of algebraic printouts~16
1.5.3 list of the solution sequence~19
2 the Solver~21
2.1 the structure of the Solvers~21
2.2 the modules of the Solvers~23
2.2.1 the Solver Preprocessor~23
2.2.2 the Immediate Assignment Solver~25
2.2.3 the linear Solver~26
2.2.4 the Valuation Solver~28
2.2.5 the Solver Postprocessor~31
2.3 application of the Solvers~32
2.3.1 command syntax~32
2.3.2 special features of the syntax of equations~33
2.3.3 example calls of the Solvers~33
2.4 the options of the Solvers~37
2.5 user specific transformation routines~40
2.6 modification of the operator evaluations~44
2.7 user specific evaluation strategies~45
i



ii~TABLE OF CONTENTS
bibliography~47
A example calculations~49
A.1 sizing of the staff two-impact~49
A.2 sizing of the transistor amplifier~57
B program listing~65
B.1 SOLVER.mac~65

Chapter 1
heuristic algorithms for the symbolic solution specifications given by sets of equations
1,1 introduction
1,1,1 numeric procedures in the comparison with symbolic methods the accurate sizing of technical designs for requires frequently the solution of nonlinear sets of equations after function defining element parameters. Usually for the determination of the looked up variables numeric optimizing procedures are used, which do not function reliably however already for small design problems with a comparatively small number of unknown quantities always. Problems prepare the complexity order of many usual optimizing algorithms (a problem, known as the curse OF dimensionality [MIC 94] is), exponentially dependent on the variable number, in first line, the selection of suitable initial values, which unwanted finding locally instead of global optima and the principle-conditioned behavior with the solution of sets of equations with degrees of freedom, with which a clarity of the solution vector missing in the reality can be pretended.
The optimum procedure for the accomplishment of a design function would basically be a complete analytic solution of the appropriate set of equations. Analytic functions, which describe explicitly the looked up item values as functions of the specification parameters, would have to be determined only once and would be available then to the arbitrarily frequent analysis with modified parameters, e.g. within design data bases of CAD systems. Besides analytic sizing formulas clarify qualitatively functional connections between the item values and the specifications and reveal in the cases concerned the existence of degrees of freedom. Since there are however no generally accepted procedures for the solution of any nonlinear sets of equations and in the special cases, in which symbolic solutions can be calculated, which complexity of the results exceeds by hand calculation to mastering frameworks far, the analytic handling of also only small sizing problems plays so far a subordinated role. With the help of modern, efficient computer algebra systems, which are able to manipulate and resolve after any variables symbolic sets of equations algebraically,
1

2 CHAPTERS 1. HEURISTIC ALGORITHMS
with the help of modern, efficient computer algebra systems, which are able to manipulate and resolve after any variables symbolic sets of equations algebraically, become some the problem categories, in particular such, specified above, which require the solution of majority linear or multivariate polynomialen systems, nevertheless the analytic handling accessible. Examples of appropriate applications are within many fields of the engineering sciences, among other things this concerns the design of similar electronic circuits, regulation-technical problem definitions, the technical mechanics and the robotics [ PFA 94 ].
1,1,2 examples of areas of application of symbolic sizing methods on the basis the following two examples are to be demonstrated some areas of application of symbolic methods. At the same time exemplary the concrete request are to be worked out at them, to which with the development of a concept for a universal solution algorithm for symbolic sets of equations must be considered.
Example 1,1 with the first example concerns it a simple task out of the technical mechanics. The two staff truss represented in figure 1,1 is given [ BRO 88, P. 112 ], at which under the angle opposite the horizontals the strength F in the point C attacks. The staffs include the angles with the horizontals and fi, the height of the triangle stretched by the staffs are defined with c. Cross section aechen A1 and a2 of the two staffs are squares with the side lengths h1 and h2. Modulus of elasticity of the used material is E. Figure 1.1: Loaded two staff truss
Due to the load by the strength F deforms the truss in such a way that itself the point of the triangle in relation to the unloaded status around the vector (u; w) T shifts, sees figure 1.2. On the assumption that the staff length variations are small due to the load in relation to the output lengths, it is to be determined now the cross section dimensions h1 and h2 of the staffs in such a way that itself for given F, fi, c and E exactly a prescribed shift (u; w) T adjusts, i.e. a1 a2 is looked up = f (F; fi; c; E; u; w): (1.1)

1.1. INTRODUCTION 3
figure 1.2: Flexibly deformed two staff truss
solution: From the static balance conditions at the point C follows after figure 1.3

figure 1.3: Force equilibrium at the point C
the material equations for the staff length variations read 1.
Fxi = 0 =) follows F cos l1 = S1l1 EA1 after figure 1,3 X; (1.4)
 Fxi = 0 =) follows F cos l2 = S2l2 EA2 after figure 1,3 X; (1.5)
whereby for the staff lengths l1 and l2 as well as for the cross-section areas A1 and a2 applies to l1 = c cos (1.6) l2 = c cos fi (1.7) A1 = h 2 1; (1.8) A2 = h 2 2: (1.9)

4 CHAPTERS 1. HEURISTIC ALGORITHMS
figure 1.4:
Because of the small geometry modifications the circular arcs, on which the staff ends can move, were replaced to shift plan in the shift plan drawn in figure 1,4 by for original staff direction the senkrechten tangents. To the side lengths dashed of the drawn in parallelogram applies
From it the shifts u and v result to the function exist now therein to resolve the symbolic set of equations from the equations (1.2) to (1.13) after the unknown quantities h1 and h2 explicitly whereby all unnecessary variables, i.e. S1, S2, A1, l1, l2, a and b, are to be eliminated.
Example 1,2
The second example originates from electro-technology and concerns the sizing of similar electronic circuits. For the two-stage transistor amplifier drawn in figure 1,5 [ NÜH 89 ] symbolic sizing formulas are to be intended, those the values of the seven resistances g 1: R7 as function of the operating voltage VCC, which Zi and the output resistance Zo of the circuit for numerically determined bias points of the transistors describe small signal reinforcement A, the input impedance:
0 B @ G 1. R7 1 C A = f (VCC;a; Zi; Zo): (1.14)

1.1. INTRODUCTION 5
Figure 1.5: Two-stage transistor amplifier
Figure 1.6: Bias point alternate circuit diagram of the amplifier with determined transistor bias points
For this purpose with the help of symbolic network analysis procedures [ SOM 93a] are calculated as well as symbolic approximation methods [ HEN 93 ] first (highly simplified) the transfer functions A, Zi and Zo in the pass band of the amplifier as functions of the item parameters and the bias point values.
A = 145303681853R2/145309663773R1 (1.15)
Zi = R7 (1.16)
Zo = 1675719398828125 R2 R7 + 394048139880824192 R1 R2/136552890630303121408 R1 (1.17)
The values of the resistances R1..R7 do not only determine the small signal characteristics, but influence besides the bias point adjustment of the circuit. Therefore are resistances

6 CHAPTERS 1. HEURISTIC ALGORITHMS
to dimension in such a way that the small signal and bias point specifications are fulfilled at the same time. The equations (1.15) - (1.17) for this reason the extensive Sparse tablet set of equations is added (1.18) - (1.51), which comes out from the bias point alternate circuit diagram of the amplifier represented in figure 1,6.
For the determination of the looked up sizing regulations in the form (1.14) 1.51 from the set of equations (1.15) - (1.51) all branch voltages are and flow V?? and I?? to eliminate

1.2. CONVENTIONAL EQUATION SOLVER 7
for the determination of the looked up sizing regulations in the form (1.14) is from the set of equations (1.15) - (1.51) all branch voltages and flows V?? and I?? to eliminate and the remaining equations after the resistances g 1: To resolve R7. 2,1,2 boundaries of the application of conventional equation solver the attempt is undertaken to insert for the solution of the sets of equations from the two examples the standard routines of well-known commercial computer algebra systems as Macsyma [ MAC 94 ] or Mathematica [ WOL 91 ] then in the case the use of Macsyma in the example 1,1, results of the following type result usually, like here:

(COM1) Solve(
[ F*cos(gamma) - S1*cos(alpha) - S2*cos(beta) = 0,
F*sin(gamma) - S1*sin(alpha) + S2*sin(beta) = 0,
Delta_l1 = l1*S1/(E*A1),
Delta_l2 = l2*S2/(E*A2),
l1 = c/cos(alpha),
l2 = c/cos(beta),
a = Delta_l2/sin(alpha+beta),
b = Delta_l1/sin(alpha+beta),
u = a*sin(alpha) + b*sin(beta),
w = a*cos(alpha) + b*cos(beta),
A1 = h1^2, a2 = h2^2
],
[ h1, h2 ]);
(D1) [ ]

This behavior of the computer algebra programs is to be explained with the fact that the sets of equations which can be solved are regarded concerning the interesting variables h1 and h2 as over-certainly, because the equation solving no additional information about (after possibility) which can be eliminated variables (S1, S2, A1, a2, l1, l2, a, b) cannot be transferred or variables, i.e. the parameters of the system (F, over under any circumstances which can be eliminated, + fi, c, E, u, w). A possible way out consists of arranging the equation solver intending also solutions for the not interesting variables. This is however not always feasible and usually very inefficient, because it in some cases much computing time necessarily for the regulation of variables, which have no uss on the looked up unknown quantities. Even at all no solution is found, if there is no analytic solution for a only one not interesting variable. The latter applies for example to the following set of equations, if only the solutions for x and y are looked up: x + y = 1 (1.52)

8 CHAPTERS 1. HEURISTIC ALGORITHMS
from the two linear equations (1.52) and (1.53) leave themselves the solutions untouched x = 2 and y = -1 to determine directly, not in the contradiction with the remaining nonlinear equation (1.54). Macsyma detects this circumstance however not and gives only error messages back | in the first attempt (COM3) because of the apparent over certainty of the system, in the second attempt (COM4) due to the analytically not solvable third equation:
(COM2) Eq: [ x + y = 1, 2*x - y = 5, y*z + sin(z) = 1]$
(COM3) Solve(Eq, [ x, y ]);
Inconsistent equations: (3)
(COM4) Solve(Eq, [ x, y, z ]);
ALGSYS CAN NOT solve - system too complicated.
1.3 request of a universal symbolic equation solver
For the symbolic solution of the equation systems it is necessary that the Solve function in none of the two above cases aborts prematurely. In the first case the solutions should be output on x and y after a consistency check with equation (1.54). In latter case is to require that beside the analytically calculated solutions additionally the remaining equations, for which no such solutions could be found in implicit form are returned, so that these can be solve if necessary with numeric procedures. An adequate response to the command COM4 would be in this sense e.g. an output of the form
[ x = 2; y = ]
the functions for the solution of sets of equations, provided by Macsyma, are not modifiable without access to the system nucleus in the way that they show the behavior required above. The target of the available work is therefore conceiving and implementation of a universal symbolic equation solver, which is, which is based on the Macsyma standard routines, able, to resolve or not make at least by elimination as much as possible necessary variables a large symbolic preprocessing of the equations sets of equations of the type stated in the examples after any subset of all variables, so that numeric optimizing procedures do not have to be only applied to a small, analytically any longer solvable nonlinear core of the system. Apart from this general objective detailed request can be derived to the program which can be developed from some well-known facts and a series from observations, which are to be made 1,1 and 1,2 as well as the set of equations (1.52) by the examples { (1.54):
1. Usually only the solution for some few variables is in demand, all other unknown quantities is to be eliminated.
2. The sets of equations which can be solved can be simple or several times parameterized.
3. It is not by any means guaranteed that the parameters are from each other independent, i.e. it is possible that a set of equations has a solution only if certain arithmetic obligation conditions between some parameters are kept.

1.3. REQUEST OF SYMBOLIC EQUATION SOLVER 9
4. the sets of equations contained often easy, direct allocations of the form xi = const., see equations (1.6) and (1.7) or (1.42) - (1.51).
5. A substantial proportion of the equations which can be solved is linear concerning a not directly evident subset of all variables, sees regarding all V?? and I?? linear equations (1.18) - (1.32).
6. The systems can contain degrees of freedom.
7. No generally accepted solution procedures for nonlinear equations and sets of equations exist.
8. Nonlinear equations can be unsolvable (contradictory), unique solutions have or multiple solutions with finite or infinite solution varieties possess.
9. Always all items of the solution quantity with the remaining equations are not consistent in the case of multiple solutions.
10. For many nonlinear equations no analytic solutions exist, see equation (1.54).

From these statements the following result, the appropriate points assigned demands:
1. The program is to solve sets of equations only so far, as it is absolutely necessary for the determination of individual variables. Calculated solutions are to be checked for possible contradictions with the remaining equations.
2. Looked up variables and parameter must be able to be processed separately from each other indicated and. Parameters may not be under any circumstances eliminated contrary to not interesting variables.
3. If dependencies between parameters are detected, then the user the program run under consideration and storage of the appropriate obligation conditions must to be continued when desired be able.
4. Direct allocations should be looked up and executed directly at the beginning of the program run, in order to reduce the range of the remaining set of equations as far as possible at small expenditure.
5. There there for linear equations efficient, closed solution procedures is to solve is appropriate it to search the set of equations repeated for linear section blocks these and to use the results into the remainder of the equations, until no equation linear equations are more available.
6.  Degrees of freedom are to be expressed automatically in variables selected by the program.
7. The solution of nonlinear equations must be controlled with the help of heuristic evaluation strategies.
8. In the case of multiple solutions with finite varieties is each individual solution path separately recursively to be pursued.

10 CHAPTERS 1. HEURISTIC ALGORITHMS
9. Sections of multiple solutions, inconsistent with the remaining equations, must be detected and the appropriate solution path be rejected.
10. As was already required for the start of the paragraph, analytically solvable equations are not to lead not to the abort of the program. Instead the set of equations is as far as possible on triangle form to be brought and the not solvable remaining equations as well as the partial solutions determined up to then to be output.
1,4 extraction and solution of linear equations
is mostly nonlinear with technical tasks the equations which can be solved, but contains the systems concerned frequently large linear section blocks. Since linear sets of equations can be solved very efficiently with the help of the Gauss-Elimination simultaneously, it is advisable to process before the solution of the nonlinear equations first the linear proportion of the system separately. Even if a complete analytic dissolution of the entire nonlinear system cannot be achieved after all looked up variables, it is nevertheless meaningful not to reduce by elimination of the linear variables and equations the system to an only small, any longer analytically solvable core whose numeric solution is substantially less complex, than an optimization executed on the complete system. Under point 5 required iterative solution linear subsystems entire set of equations is to that extent no trivial function, than that neither the equations concerned nor the subset of the variable, concerning which these equations are linear admits from the beginning is. Therefore a search strategy must be found, (for efficiency reasons as large ones as possible) the linear equations and variable blocks extracted from any nonlinear set of equations.
1,4,1 intuitive methodologies for the search of linear equations
For the elucidation of the task the following nonlinear set of equations is consulted, which is to be solved x, y and z after the variables. At first sight only the equation (1.55) is linear, regarding all three variables. In the case of use of a simple search algorithm, which finds excluding such completely linear equations, max. a variable can after appropriate dissolution of (1.55), e.g. after x in this case, from which both remaining equations are eliminated. A more exact view of the equations reveals however a better alternative. After the distance of equation (1.56) and shifting the terms dependent on z on the right pages of the equations (1.55) and (1.57) two in the variables x and y linear equations develop:

1.4. EXTRACTION AND SOLUTION of LINEAR EQUATIONS 11
their simultaneous inversion leads to the solutions parameterized in z after their inserting into (1.56) only one nonlinear equation which can be solved remains:
In view of the fact that with the second version in only one iteration two unknown quantity could be determined at the same time, it is to be preferred latter methodology of the search for completely linear equations, applied first, despite the additional shaping expenditure. This applies in particular if a set of equations contains at all no equations, in which all variables involved in purely linear form occurs. The procedure used for the extraction of linear subsystems should interconnect therefore both demonstrated operations for the removal of nonlinear equation proportions:
1. Distance of individual nonlinear equations
2. Shifting variables occurring in nonlinear terms to the right side of the equations by a balanced combination of the two operations can be achieved that the resulting linear subsystems have max. size and often at least are approximately square.
1.4.2 a heuristic algorithm for the search of linear equations
For a computer implementation such a search for equation linear equations, executed intuitively by humans, must be systematized and formulated algorithmic. Since the term does not define linear section set of equations, how is evident on the basis the different solution types, the desired result in unique way, a heuristic strategy was developed for the imitation of the intuitive methodology. This strategy is demonstrated for the comparison of the results at the system,  already regarded, (1.55)- (1.57).
For the set of equations first a table is set up, whose lines are assigned to the equations and their columns the variables. The entry at the position (i; j) of the table contains for the equation i the coefficient 1 concerning the linear member, i.e. the first power, of the variable xj. Is available as for z in equation (1.57) no term in first power or steps these functions not polynomial in argument on (e.g. sin x or sqrt x), then the appropriate position with a cross () is marked. x y z
Gl. 1)
1 Macsyma places the instruction to the determination of the coefficients of rational printouts RATCOEFF to the order.

12 CHAPTERS 1. HEURISTIC ALGORITHMS
second, equal large evaluation matrix, is assigned to this table whose entries are equal to zero, if the corresponding is entry in the coefficient table a constant, and equal unity, if the linear coefficient concerned contains looked up variables or not existed (). additionally the line and column totals become noted at the edges of the matrix, as well as under the sigma signs on the top right and on the left of down respectively the line total of the column totals (P S) and the column total of the line totals (P Z). obvious correspond to
x y z P S 0 1 2 3 1) 0 0 0 0 2) 2 0 1 1 3) 1 0 0 1 P Z 3 (1.63)
A linear section set of equations and the appropriate variables are found if with a consequence of the operations specified at the end of paragraph 1,4,1 all ones were eliminated. Transferred to manipulations thereby the 1 corresponds to the evaluation matrix. Operation deleting the line belonging to to a certain equation. The 2. Operation is equivalent column assigned for the distance of some variable. The linear subsystem consists afterwards of those equations and variables, whose lines and columns were not removed from the matrix. The reduction of the evaluation matrix (1.63) to a zero-matrix can take place in exactly three different ways:
1. Capers of the lines 2) and 3),
2nd capers of the columns y and z,
3rd capers of the line 2) and the column z.
of the demand for max. size and as square a form of the linear equation blocks as possible is directly portable to the characteristics of the zero-matrix which can be obtained. In this sense the latter of the three options is optimal, because it supplies the system (1.58)-(1.59), already detected in the previous paragraph as optimum solution. The two other possibilities lead against it for the under-certain equation (1.55) or to a over-certain 3 1-System in x.
The search for an optimal sequence of line and column cancellations is a complex combinatorial problem. In order to avoid the associated expenditure, a heuristic, local decision criterion becomes the determination of the line or column which can be removed in the respective step, i.e. a Greedy strategy
[FOU 92], uses: The line or column is deleted, which contains most ones, thus that with the largest line or column total. This criterion supplies with however still no unique predicate,
  if two or more lines have the same (largest) line total,
  or two or more columns the same (largest) column total has,
  or if the totals of the maximumevaluated line and the maximumevaluated column are identical.

In the first two cases any can be selected, usually is this for the sake of simplicity first in each case the found with max. evaluation from the concerned lines or columns.
The third case occurs in the available example. In the evaluation matrix (1.63) possess both the line 3) and the column z the max. total 2. At the beginning from both possibilities arbitrarily r>2.al 2. Atess both. In t*********e exampg from he l2 = c c to a symbolic linemQUATIOON AND SOLUTION oe