Controlling or analyzing a process by solving a system of linear equations in real-time
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/12
G06F-007/38
G06F-007/32
G06F-007/52
G06G-007/32
G06G-007/34
G06G-007/36
출원번호
US-0468160
(2009-05-19)
등록번호
US-8204925
(2012-06-19)
발명자
/ 주소
Vrancic, Aljosa
Wenzel, Lothar
출원인 / 주소
National Instruments Corporation
대리인 / 주소
Meyertons Hood Kivlin Kowert & Goetzel, P.C.
인용정보
피인용 횟수 :
6인용 특허 :
27
초록▼
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 recursi
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.
대표청구항▼
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
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; ora 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; andperform 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; andstore 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; andrecursively 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; andwherein 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; anddetermine 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; andrecursively 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; andrecursively 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; andwherein 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; orthe 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; orperform 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; ora 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; andperforming, 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; andstoring, 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; andrecursively 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; andwherein 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; andrecursively 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; andrecursively 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; andwherein 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; orthe 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; orperforming 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; andperform 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; andstore 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; andperform 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; andstore the solved values for the set of values, wherein the solved values are useable to control or analyze the process.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (27)
Daniel Sam M. (Tempe AZ) McRoberts Louis A. (Scottsdale AZ), Adaptive antenna array including batch covariance relaxation apparatus and method.
Red Walter E. (Provo UT) Davies Brady R. (Orem UT) Wang Xuguang (Provo UT) Turner Edgar R. (Provo UT), Device and method for correction of robot inaccuracy.
Keuper Gerhard,DEX ; Senger Karl-Heinz,DEX ; Stoller Roland,DEX, Method and apparatus for correcting vehicle chassis sensor signals and for controlling a vehicle chassis.
Kapur Sharad ; Long David Esley ; Zhao Jingsong, Method and apparatus for designing interconnections and passive components in integrated circuits and equivalent structures by efficient parameter extraction.
King Adrian S. (Albuquerque NM), Method and apparatus for solving dense systems of linear equations with an iterative method that employs partial multipl.
Agrawal Prathima (New Providence NJ) Telichevesky Ricardo (Cambridge MA) Trotter John A. (Somerville NJ), Method of operating a multiprocessor computer to solve a set of simultaneous equations.
Achlioptas, Dimitris; McSherry, Frank D., Methods and systems for computing singular value decompositions of matrices and low rank approximations of matrices.
Scott David S. (Portland OR), Parallel processing computer for solving dense systems of linear equations by factoring rows, columns, and diagonal, inv.
Aoki, Takayuki, Program generation method for calculation of a Poisson equation, diffusion equation, or like partial differential equation performed on irregularly dispersed grid points.
MacCleery, Brian C.; Nagle, James C.; Monroe, J. Marcus; Barp, Alexandre M.; Kodosky, Jeffrey L.; Andrade, Hugo A.; Odom, Brian Keith; Butler, Cary Paul, Global optimization and verification of cyber-physical systems using floating point math functionality on a system with heterogeneous hardware components.
Kodosky, Jeffrey L.; Andrade, Hugo A.; Odom, Brian Keith; Butler, Cary Paul; MacCleery, Brian C.; Nagle, James C.; Monroe, J. Marcus; Barp, Alexandre M., Graphical development and deployment of parallel floating-point math functionality on a system with heterogeneous hardware components.
Kodosky, Jeffrey L.; Andrade, Hugo A.; Odom, Brian Keith; Butler, Cary Paul; MacCleery, Brian C.; Nagle, James C.; Monroe, J. Marcus; Barp, Alexandre M., Graphical development and deployment of parallel floating-point math functionality on a system with heterogeneous hardware components.
Zimmer, Michael F., Systems and methods for reducing memory traffic and power consumption in a processing environment by solving a system of linear equations.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.