Controlling or analyzing a process by solving a system of linear equations in real-time

• US 8,204,925 B2
• Filed: 05/19/2009
• Issued: 06/19/2012
• Est. Priority Date: 05/22/2008
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Vrancic, Aljosa, Wenzel, Lothar
• Primary Examiner(s): Shah, Kamini S
• Assistant Examiner(s): Saxena, Akash
• Application Number:
  US12/468,160
• Publication Number:
  US 20090292511A1
• Time in Patent Office: 1,127 Days
• Field of Search: 703/2, 708/446, 708/520, 708/607, 708802-804
• US Class Current: 708/446
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations

Abstract

System and method for controlling/analyzing a process by solving a system of linear equations in real-time. Linear equations that model the process are stored. In an off-line stage a partitioning strategy is determined based on the linear equations, including determining groups of values for recursively partitioning a set of values measured and/or computed from the process. In an on-line stage: current process data are received from the process, including measurements from the process, and composing a set of values; the linear equations are recursively solved for a first group of the set, where the first group partitions the set into respective subsets of values, and where the recursively solving produces solved values for respective first groups of the set/subset of values; the linear equations are solved for remaining unsolved values in the set, thereby producing solved values for the set, which are stored and are useable to control/analyze the process.

Claims

1. A non-transitory computer accessible memory medium that stores program instructions for controlling or analyzing a process by solving a set of linear equations in real-time, wherein the program instructions are executable by a processor to:

store a first plurality of linear equations that models the process, wherein the process comprises one or more of;

a manufacturing process;

an automation process;

or

a simulation process;

perform an off-line stage, wherein to perform the off-line stage the program instructions are executable to;

determine a partitioning strategy based on the first plurality of linear equations, wherein said determining the partitioning strategy comprises determining groups of values for recursively partitioning a determined set of values measured or computed from the process; and

perform an on-line stage, wherein to perform the on-line stage, the program instructions are executable to;

receive current process data from the process, wherein at least a portion of the current process data from the process comprises measurements on the process, wherein the current process data comprises a set of values;

recursively solve the first plurality of linear equations for a first group of the set of values, wherein the first group of the set of values partitions the set of values into respective subsets of values, wherein said recursively solving produces solved values for respective first groups of the set/subset of values;

solve the first plurality of linear equations for remaining unsolved values in the set of values;

wherein said recursively solving and said solving produce solved values for the set of values; and

store the solved values for the set of values, wherein the solved values are useable to control or analyze the process.

2. The memory medium of claim 1, wherein the program instructions are executable to:

repeat the online stage multiple times in an iterative manner to control or analyze the process.

3. The memory medium of claim 1,

wherein to store a first plurality of linear equations that models the process, the program instructions are executable to:

store a solution grid for a set of linear equations comprising N1 equations with N2 unknowns, wherein the solution grid comprises a set of points;

wherein to recursively solve the first plurality of linear equations for a first group of the set of values, the program instructions are executable to;

solve the set of linear equations exactly for a specified subset of points in the grid, wherein the subset of points divides the grid into a first plurality of independent sub-grids for which the subset of points comprises at least a portion of each of their boundary conditions; and

recursively perform said solving for each sub-grid of the first plurality of independent sub-grids until a specified stopping condition obtains, thereby generating a second plurality of sub-grids; and

wherein to solve the first plurality of linear equations for remaining unsolved values in the set of values, the program instructions are executable to;

solve the set of linear equations exactly for the points in each of the second plurality of sub-grids.

4. The memory medium of claim 3, wherein the stopping condition comprises the calculation cost of solving the set of linear equations exactly for the points in each of the second plurality of sub-grids being approximately equal to recursion overhead for continuing said recursively performing.

5. The memory medium of claim 1,

wherein to store a first plurality of linear equations that models the process, the program instructions are executable to:

store a sparse and weakly coupled coefficient matrix M that specifies a system of N1 linear equations with N2 unknowns, M*x=b, wherein b comprises a vector of known values, and wherein x comprises a vector of unknown values, and wherein the system of N1 linear equations models the process;

wherein to determine a partitioning strategy based on the first plurality of linear equations, the program instructions are executable to;

analyze the matrix M to determine an underlying structure of the matrix corresponding to a geometry of the process, including permuting two or more rows or columns of the matrix M; and

determine the partitioning strategy based on the underlying structure of the matrix M, wherein, to determine the partitioning strategy, the program instructions are executable to;

determine a first subvector xs of vector x that when solved partitions a remainder of vector x into a first plurality of subvectors xp;

determine respective second subvectors xs for each of the first plurality of subvectors xp, wherein each second subvector xs, when solved, partitions a respective subvector xp of the first plurality of subvectors xp into respective second pluralities of subvectors xp; and

recursively determine successive pluralities of subvectors xs and respective subvectors xp until a stopping condition obtains, wherein the length of each subvector xs is small compared to the combined lengths of the respective plurality of subvectors xp.

6. The memory medium of claim 5, wherein to perform the offline stage, the program instructions are further executable to:

pre-calculate coefficients for evaluating exact values of subvectors xs.

7. The memory medium of claim 6,

wherein to perform the on-line stage, the program instructions are further executable to:

initialize vector b with the current process data;

wherein to recursively solve the first plurality of linear equations for a first group of the set of values, the program instructions are executable to;

calculate exact values for the first subvector xs using the pre-calculated coefficients; and

recursively calculate exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the stopping condition obtains;

wherein to solve the first plurality of linear equations for remaining unsolved values in the set of values, the program instructions are executable to;

calculate exact values for unpartitioned subvectors xp;

wherein the calculated exact values for the subvectors xs and the unpartitioned subvectors xp compose exact values for vector x, wherein vector x comprises an exact solution for the system of N1 linear equations; and

wherein to store the solved values for the set of values, the program instructions are executable to;

store vector x, wherein vector x is useable to control or analyze the process.

8. The memory medium of claim 7,

wherein the stopping condition comprises one of:

the length of a subvector xp being equal to 1;

or

the runtime cost of solving the set of N1 linear equations exactly for the subvectors xp being approximately equal to recursion overhead for continuing said recursively determining the successive pluralities of subvectors xs and respective subvectors xp;

wherein the program instructions are further executable to;

determine a number of recursion steps performed in said recursively determining;

wherein to recursively calculate exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the stopping condition obtains, the program instructions are executable to;

recursively calculate exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the determined number of recursion steps has been performed.

9. The memory medium of claim 1, wherein to perform measurements on the process, the program instructions are executable to:

perform direct measurements of the current process data;

or

perform direct measurements of first process data, then determine the current process data based on the first process data.

10. The memory medium of claim 1, wherein the first plurality of linear equations has an associated coefficient matrix, and wherein to recursively solve or solve, the program instructions are executable to:

compute one or more partial matrix inversions.

11. The memory medium of claim 1, wherein the first plurality of linear equations has an associated coefficient matrix, wherein to recursively solve or solve, the program instructions are executable to:

compute one or more partial matrix pseudo-inversions.

12. The memory medium of claim 1, wherein to recursively solve or solve, the program instructions are executable to:

estimate at least a portion of the solved values using model reduction techniques.

13. A computer-implemented method for controlling or analyzing a process by solving a set of linear equations in real-time, comprising:

utilizing a computer to perform;

storing, in a memory of the computer, a first plurality of linear equations that models the process, wherein the process comprises one or more of;

a manufacturing process;

an automation process;

or

a simulation process;

performing, via the computer, an off-line stage, comprising;

determining a partitioning strategy based on the first plurality of linear equations, wherein said determining the partitioning strategy comprises determining groups of values for recursively partitioning a determined set of values measured or computed from the process; and

performing, via the computer, an on-line stage wherein the computer is coupled to the process, comprising;

receiving current process data from the process, wherein said receiving current process data from the process comprises performing measurements on the process, wherein the current process data comprises a set of values;

recursively solving the first plurality of linear equations for a first group of the set of values, wherein the first group of the set of values partitions the set of values into respective subsets of values, wherein said recursively solving produces solved values for respective first groups of the set/subset of values;

solving the first plurality of linear equations for remaining unsolved values in the set of values;

wherein said recursively solving and said solving produce solved values for the set of values; and

storing, in the memory of the computer, the solved values for the set of values, wherein the solved values are useable to control or analyze the process.

14. The method of claim 13, further comprising:

repeating the online stage multiple times in an iterative manner to control or analyze the process.

15. The method of claim 13,

wherein said storing a first plurality of linear equations that models the process comprises:

storing a solution grid for a set of linear equations comprising N1 equations with N2 unknowns, wherein the solution grid comprises a set of points;

wherein said recursively solving the first plurality of linear equations for a first group of the set of values comprises;

solving the set of linear equations exactly for a specified subset of points in the grid, wherein the subset of points divides the grid into a first plurality of independent sub-grids for which the subset of points comprises at least a portion of each of their boundary conditions; and

recursively performing said solving for each sub-grid of the first plurality of independent sub-grids until a specified stopping condition obtains, thereby generating a second plurality of sub-grids; and

wherein said solving the first plurality of linear equations for remaining unsolved values in the set of values comprises;

solving the set of linear equations exactly for the points in each of the second plurality of sub-grids.

16. The method of claim 15, wherein the stopping condition comprises the calculation cost of solving the set of linear equations exactly for the points in each of the second plurality of sub-grids being approximately equal to recursion overhead for continuing said recursively performing.

17. The method of claim 13,

wherein said storing a first plurality of linear equations that models the process comprises:

storing a sparse and weakly coupled coefficient matrix M that specifies a system of N1 linear equations with N2 unknowns, M*x=b, wherein b comprises a vector of known values, and wherein x comprises a vector of unknown values, and wherein the system of N1 linear equations models the process;

wherein said determining a partitioning strategy based on the first plurality of linear equations comprises;

analyzing the matrix M to determine an underlying structure of the matrix corresponding to a geometry of the process, including permuting two or more rows or columns of the matrix M;

determining the partitioning strategy based on the underlying structure of the matrix M, comprising;

determining a first subvector xs of vector x that when solved partitions a remainder of vector x into a first plurality of subvectors xp;

determining respective second subvectors xs for each of the first plurality of subvectors xp, wherein each second subvector xs, when solved, partitions a respective subvector xp of the first plurality of subvectors xp into respective second pluralities of subvectors xp; and

recursively determining successive pluralities of subvectors xs and respective subvectors xp until a stopping condition obtains, wherein the length of each subvector xs is small compared to the combined lengths of the respective plurality of subvectors xp.

18. The method of claim 17, wherein the offline stage further comprises:

pre-calculating coefficients for evaluating exact values of subvectors xs.

19. The method of claim 18,

wherein said performing the on-line stage further comprises:

initializing vector b with the current process data;

wherein said recursively solving the first plurality of linear equations for a first group of the set of values comprises;

calculating exact values for the first subvector xs using the pre-calculated coefficients; and

recursively calculating exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the stopping condition obtains;

wherein said solving the first plurality of linear equations for remaining unsolved values in the set of values comprises;

calculating exact values for unpartitioned subvectors xp;

wherein the calculated exact values for the subvectors xs and the unpartitioned subvectors xp compose exact values for vector x, wherein vector x comprises an exact solution for the system of N1 linear equations; and

wherein said storing the solved values for the set of values comprises;

storing vector x, wherein vector x is useable to control or analyze the process.

20. The method of claim 19,

wherein the stopping condition comprises one of:

the length of a subvector xp being equal to 1;

or

the runtime cost of solving the set of N1 linear equations exactly for the subvectors xp being approximately equal to recursion overhead for continuing said recursively determining the successive pluralities of subvectors xs and respective subvectors xp;

the method further comprising;

determining a number of recursion steps performed in said recursively determining;

wherein said recursively calculating exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the stopping condition obtains comprises;

recursively calculating exact values of the successive pluralities of subvectors xs using the pre-calculated coefficients and exact values of subvectors xs calculated in previous recursion steps, until the determined number of recursion steps has been performed.

21. The method of claim 13, wherein said performing measurements on the process comprises:

performing direct measurements of the current process data;

or

performing direct measurements of first process data, then determining the current process data based on the first process data.

22. A non-transitory computer accessible memory medium that stores program instructions for controlling or analyzing a process by solving a set of linear equations in real-time, wherein the program instructions are executable by a processor to:

store a first plurality of linear equations that models the process, wherein the process comprises a petrochemical exploration or production process;

perform an off-line stage, wherein to perform the off-line stage the program instructions are executable to;

determine a partitioning strategy based on the first plurality of linear equations, wherein said determining the partitioning strategy comprises determining groups of values for recursively partitioning a determined set of values measured or computed from the process; and

perform an on-line stage, wherein to perform the on-line stage, the program instructions are executable to;

receive current process data from the process, wherein at least a portion of the current process data from the process comprises measurements on the process, wherein the current process data comprises a set of values;

recursively solve the first plurality of linear equations for a first group of the set of values, wherein the first group of the set of values partitions the set of values into respective subsets of values, wherein said recursively solving produces solved values for respective first groups of the set/subset of values;

solve the first plurality of linear equations for remaining unsolved values in the set of values;

wherein said recursively solving and said solving produce solved values for the set of values; and

store the solved values for the set of values, wherein the solved values are useable to control or analyze the process.

23. A non-transitory computer accessible memory medium that stores program instructions for controlling or analyzing a process by solving a set of linear equations in real-time, wherein the program instructions are executable by a processor to:

store a first plurality of linear equations that models the process, wherein the process comprises a financial or securities-related process;

perform an off-line stage, wherein to perform the off-line stage the program instructions are executable to;

determine a partitioning strategy based on the first plurality of linear equations, wherein said determining the partitioning strategy comprises determining groups of values for recursively partitioning a determined set of values measured or computed from the process; and

perform an on-line stage, wherein to perform the on-line stage, the program instructions are executable to;

receive current process data from the process, wherein at least a portion of the current process data from the process comprises measurements on the process, wherein the current process data comprises a set of values;

recursively solve the first plurality of linear equations for a first group of the set of values, wherein the first group of the set of values partitions the set of values into respective subsets of values, wherein said recursively solving produces solved values for respective first groups of the set/subset of values;

solve the first plurality of linear equations for remaining unsolved values in the set of values;

wherein said recursively solving and said solving produce solved values for the set of values; and

store the solved values for the set of values, wherein the solved values are useable to control or analyze the process.