Paper Info
Title
Symbolic computation techniques for solving large expression problems from mathematics and engineering
Abstract
This thesis studies the use of computer algebra methods to solve some large-expression problems from mathematics and engineering. We give several strategies for solving problems from symbolic linear algebra and dynamic systems. First, we describe new forms for fraction-free LU factoring and QR factoring. These new forms keep both the computation and the output results in the same domain as the input domain and thereby increase the computational efficiency in applications by delaying the appearance of quotients of the input data. To compute the new forms, we use a fraction-free variant of Gaussian elimination to control the growth of matrix entries. We give a complexity analysis for standard domains. Secondly, we propose a general method, hierarchical representation and signature computing for zero testing, to deal with problems with intermediate or inherent expression swell. For instance, when we use Gaussian elimination to solve large symbolic linear equations, the resulting large expressions can be handled using our general method. We implement a version of LU factoring using hierarchical representation with signature computing for zero testing. The LU factoring is the standard one, rather than the fraction-free one described above. We prove that the improved algorithm is much faster than the classical LU factoring algorithm using Gaussian elimination and give associated time complexity analysis and experimental results. Besides large expression problems from linear algebra, we also explore large expression problems from engineering, especially those arising from analyzing and solving multibody dynamic systems and limit cycle computations. We define a new concept, implicit reduced involutive form, to cope with large expression problems resulting from symbolically pre-processing systems of differential algebraic equations (DAE). We also show how symbolic pre-processing can be combined with numerical from limit cycle computations which could not be directly solved because of large expression swell. The techniques we develop in this thesis are quite general and can be easily applied to other similar areas, such as computing determinants and solving more general DAE models. Keywords. Large Expression Management, Differential Algebraic Equations, RIF-SIMP, LARGE EXPRESSIONS, Multibody Dynamic System, Differentiation and Elimination, Hierarchical Representations, Signature, LII Symbolic Decomposition, Time Complexity, Limit Cycle, Computer Algebra.
Year
DOI
Venue
2007
10.1145/1358183.1358188
ACM Comm. Computer Algebra
Keywords
Field
DocType
symbolic computation technique,large expression problem,limit cycle computation,hierarchical representation,gaussian elimination,zero testing,multibody dynamic system,signature computing,new form,general method,lu factoring,symbolic computation
Linear algebra,Linear equation,Discrete mathematics,Algebra,Expression (mathematics),Matrix (mathematics),Algorithm,Symbolic computation,Differential algebraic equation,Gaussian elimination,Time complexity,Mathematics
Journal
Volume
Issue
Citations 
41
4
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Wenqin Zhou1102.17