US 5,629,845 AGranted

Parallel computation of the response of a physical system

OwnerWerner Linigerinventor

Life of this patent

Estimating the term…

Loading patent…

Abstract

The responses of many types of large interacting physical systems, including but not restricted to electrical, mechanical, fluidic, and biochemical systems, are describable by very large systems of ordinary differential equations, sometimes involving hundreds of thousands of equations and unknowns. Such large systems are solved rapidly by use of a distributed network of computers or a massively parallel computer. This is accomplished by a splitting technique involving the steps of: 1) subdividing the set of all differential equations on the one hand, and the set of all unknown dependent variables on the other hand, into an equal number of subsets, all but possibly one of which are of equal size; 2) splitting off part of the right side of the differential equations from the rest and replacing the unknowns in the remaining part by known input functions of time, so as to convert the original fully coupled system into a collection of uncoupled subsystems; and 3) solving each subsystem in parrallel on one of the available processors by the Backward Euler integration method. The splitting is effective only over one single integration step at a time whereas, globally in time, all of the unknowns remain coupled. This strategy results in a direct (non-iterative), accurate and stable integration scheme, requiring only two parallel solution passes over all of the subsystems per time step.

A method of obtaining values of state variables of a physical system of interconnected components, individual ones of said components comprising electrical components or mechanical components or fluidic components or biological components, the state variables including current in the case of an electrical component and speed in the case of a mechanical component and fluidic flow rate in the case of a fluidic component and signal strength in the case of a biological component, wherein the physical system is describable by a coupled system of ordinary differential equations providing time-dependent values of the state variables of the respective components, the method employs a distributed network of computers or a parallel computer having a plurality of processors of which p is the number of processors, the method comprising steps of:

counting a number m of unknown state variables wherein m is the number of equations in the system of differential equations, said equations to be solved over an interval of time subdivided into a sequence of time steps;
representing said state variables for all of said components of said physical system by state vectors wherein components of the vectors correspond respectively to said state variables of said physical system, each vector consisting of m components;
slicing the state vectors into a number K of subvectors wherein K is greater than one, each of said subvectors having a number of components equal to or smaller than b, wherein K is equal to m/b for integral values of m/b or equal to one plus the integer part of the quotient m/b for nonintegral values of m/b, the slicing providing an array of subvectors;
splitting respective ones of the equations into respective first parts having first sets of unknown values of state variables and into respective second parts having second sets of unknown values of state variables;
estimating values of said second sets of unknown values of state variables and inserting estimates of said second sets of unknown values of state variables into said second parts of said equations, said estimates corresponding to a state of said physical system at a first instant of time of a predetermined one of said time steps;
updating the state vector concurrently over any one of said time steps by use of a plurality of said processors of said computer, wherein in any one of said time steps, there are obtained first computed values of said first sets of unknown values of state variables at a final instant of time of said one time step, said final instant of time being equal to the sum of said first instant plus the duration of said one time step;
and
performing a further updating of the state vector over said one time step, wherein there are obtained second values of said first sets of unknown values of state variables, but with said first computed values used as estimated values of said second sets of state variables in said second parts of the differential equations.

5 more elements

Abstract

Claims9