Source: http://www.google.nl/patents/US5604911?hl=nl
Timestamp: 2013-05-25 14:59:31
Document Index: 27998087

Matched Legal Cases: ['art 199523', 'art 1999', 'art 2002', 'art 200026', 'art 200114', 'art 200426', 'art 2010', 'art 201212']

Patent US5604911 - Method of and apparatus for preconditioning of a coefficient matrix of ... - Google PatentenZoeken Afbeeldingen Maps Play YouTube Nieuws Gmail Drive Meer » Geavanceerd zoeken naar patenten | Webgeschiedenis | Inloggen Geavanceerd zoeken naar patenten PatentenTo analyze a physical phenomenon by a computer having a plurality of vector processors and a parallel computer, there is generated submatrices in a preconditioning for obtaining solutions of simultaneous linear equations. Nonzero elements of the coefficient matrix are stored with column number indices...http://www.google.nl/patents/US5604911?utm_source=gb-gplus-sharePatent US5604911 - Method of and apparatus for preconditioning of a coefficient matrix of simultaneous linear equations PublicatienummerUS5604911 APublicatietypeVerlening Aanvraagnummer07/947,801 Publicatiedatum18 feb 1997 Aanvraagdatum21 sept 1992 Prioriteitsdatum19 sept 1991 UitvindersYasunori Ushiro Oorspronkelijke patenteigenaarHitachi, Ltd. Classificatie in de VS703/2 Internationale classificatieG06F17/11G06F17/16G06F17/12 Co�peratieve classificatieG06F17/16G06F17/12 Europese classificatieG06F17/16G06F17/12ReferentiesPatentcitaties (3)Niet-patentcitaties (12) Verwijzingen naar dit patent (33)Externe linksUSPTO USPTO-toewijzing EspacenetMethod of and apparatus for preconditioning of a coefficient matrix of simultaneous linear equationsUS 5604911 A Samenvatting To analyze a physical phenomenon by a computer having a plurality of vector processors and a parallel computer, there is generated submatrices in a preconditioning for obtaining solutions of simultaneous linear equations. Nonzero elements of the coefficient matrix are stored with column number indices assigned thereto such that the elements of the coefficient matrix and the data of right-side vector are scaled according to a sum of absolute values of nondiagonal elements of the coefficient matrix and a diagonal element related thereto. The nonzero elements are sorted depending on magnitude of their absolute values to subdivide the nondiagonal nonzero elements into m submatrices E1, E2, . . . , Em each having substantially a comparable order. Using products developed between differences between a unit matrix and these submatrices in the iterative calculations for a large-sized numerical simulation, there is obtained quite a satisfactory characteristic of convergence of solutions and hence the processing speed is remarkably increased.
I claim: 1. An apparatus for generating submatrices for a preconditioning of a coefficient matrix of simultaneous linear equations, said apparatus comprising: storing means for storing therein data of a coefficient matrix of simultaneous linear equations and data of a right-side vector; indexing means for assigning a column index L to each nondiagonal nonzero element for each row selected from the stored coefficient matrix with a correspondence established therebetween and storing the nonzero elements in the storing means; means for performing a summation of all absolute values of the stored nonzero elements for each row of the coefficient matrix fetched from the storing means, where an absolute value of the nonzero element is a number with a positive sign derived from changing the sign to positive if negative; scaling means for scaling the data of the coefficient matrix and the data of the right-side vector fetched from the storing means according to a plurality of diagonal elements on a main diagonal axis of the coefficient matrix and the summation of the absolute values produced by the summation performing means; sorting means for comparing with each other absolute values of the nonzero elements scaled by said scaling means for each row, thereby sorting the nonzero elements into an ascending or descending order and changing an order of the column index L to keep correspondence thereof; and submatrix generating means for subdividing a matrix consisting of the sorted nonzero elements A(N,1), A(N,2), A(N,ND) wherein N denotes a number of rows of the coefficient matrix and ND denotes a maximum number of nonzero elements per row into submatrices E1, E2, . . . , Em, wherein each submatrix is a matrix consisting of the nonzero elements A (N,j) or A (N,k)+ . . . +A (N,l) 1≦j, k, l≦ND, and a norm represented by + where (N,j).
2. An apparatus according to claim 1, further including multiplying means for sequentially achieving matrix multiplications and thereby producing a matrix product (I-E1) indicates a unit matrix and I-Em means a matrix subtraction.
7. An apparatus according to claim 1, further including: means for achieving an incomplete LU factorization for the coefficient matrix of said linear equations by decomposing the coefficient matrix into a product of a lower triangular matrix L and an upper triangular matrix U in accordance with diagonal elements thereof; and means for determining whether generating the submatrices or achieving the incomplete LU factorization in accordance with a maximum value of a ratio between an absolute value of a diagonal element on a main diagonal axis and a sum of absolute values of the nondiagonal elements for each row.
8. An apparatus for calculating preprocessing submatrices for a coefficient matrix of simultaneous linear equations generated in a process of a numerical simulation according to a finite element method, said apparatus comprising: storing means for storing therein the coefficient matrix, a right-side vector B, the preprocessing submatrices resultant from calculation, and intermediate results thereof; means for assigning column number indices to nondiagonal nonzero elements of the coefficient matrix for each row thereof, respectively by reference to contents of the storing means, and scaling the coefficient matrix and the right-side vector according to diagonal elements on a main diagonal axis and sum of the absolute values of nondiagonal elements of the coefficient matrix; means for sorting the nonzero elements in a predetermined order in accordance with magnitude of each of the absolute values thereof and thereby subdividing the nonzero elements into m submatrices E1, E2, . . . , Em each being a matrix consisting of the nonzero elements, and a norm being approximately the same value respectively; and calculating and processing means for sequentially conducting multiplications between (I-Ei), i=1, 2, . . . , m, where I is a unit matrix.
9. An apparatus for calculating preprocessing submatrices for a coefficient matrix of simultaneous linear equations generated in a process of a numerical simulation according to a calculus of finite differences, said apparatus comprising: storing means for storing therein the coefficient matrix, a right-side vector B, the preprocessing submatrix resultant from the calculation, and intermediate results thereof; means for scaling the coefficient matrix and the right-side vector according to a sum of absolute values of nondiagonal elements of the coefficient matrix and a value of a diagonal element related thereto by reference to contents of the storing means; and calculating and processing means for sequentially conducting multiplications between (I-Ai), i=1, 2, . . . , m, where I is a unit matrix and Ai is a nondiagonal band matrix having elements only in band matrices of A1, A2 . . . A6 except diagonal elements on a main diagonal axis.
10. A computer for use with simultaneous linear equations for computing incomplete LU factorization matrix for a coefficient matrix of the linear equations, wherein the whole coefficient matrix is decomposed into a product of a lower triangular matrix L and an upper triangular matrix U, said computer comprising: means for storing therein the coefficient matrix, a result of the calculation, and intermediate results thereof; and calculating and processing means for achieving an incomplete LU factorization of the coefficient matrix by decomposing into a product of lower and upper triangular matrices by reference to contents of the storing means according to a value determined by both a diagonal element on a main diagonal axis and a sum of absolute values of nondiagonal elements for each row.
13. A method of generating submatrices for a preconditioning of a coefficient matrix of simultaneous linear equations presented by physical variables in a process of analyzing a physical system, said method comprising the steps of: storing data of a coefficient matrix of simultaneous linear equations, data of a right-side vector, and nondiagonal nonzero elements selected from the stored coefficient matrix with a column index L assigned to each of the nonzero elements for each row; adding to each other the stored nonzero absolute values of elements for each row of the coefficient matrix; scaling the data of the coefficient matrix and the data of the right-side vector according to diagonal elements of the coefficient matrix and a sum of the absolute values; comparing with each other absolute values of the nonzero elements of the coefficient matrix and thereby sorting the nonzero elements into a predetermined order and changing the order of the column index L so as to keep correspondence thereof; and subdividing a matrix consisting of the sorted nonzero elements A (N,1), A (n,2), . . . ,A (N,ND) wherein N denotes the number of rows of the coefficient matrix and ND denotes a maximum number of nonzero elements per row into submatrices E1, E2, . . . , Em, wherein each submatrix consists of the nonzero elements A (N,j) or A (N,k)+ . . . +A (N,l), 1≦j, k, 1≦ND, and a norm represented by approximately a same value respectively, where means an absolute value of the A (N,j).
14. A method according to claim 13, further including the step of sequentially achieving multiplications for producing a product (I-E1) matrix.
According to an advanced method developed to apply the method above to a computer having a plurality of vector processing units, the incomplete LU factorization cannot be easily applied to the plural vector processors. Namely, in an iteration for the number of two-dimensional lattice or grid points in a region subdivided into m.sub.x by m.sub.y, the vector length is limited to m.sub.x.
In the incomplete LU decomposition above; the degree of parallelization n.sub.x considerably smaller than the order or dimensionality n=n.sub.x degree n.sub.x in the two-dimensional processing is remarkably smaller than the order n=n.sub.x proposed methods in which without using the incomplete LU factorization, a plurality of matrices are multiplied by each other in the preconditioning. However, according to these methods, the convergence speed of numerical solutions of the linear equations is lowered when compared with the solution adopting the incomplete LU factorization, which leads to a disadvantage that when the property of the coefficient matrix is deteriorated (i.e., when an ill condition exists), the convergence of solutions becomes to be unstable.
First, to establish the calculation method suitable for the parallel processing, the incomplete LU factorization of the matrix A is not achieved in the preconditioning. Namely, the non-diagonal nonzero elements of the matrix A are subdivided into m submatrices E1, E2, . . . , Em such that each preconditioning matrix w is formed with multiplications between (I-Ei), i=1, 2, . . . , m. Resultantly, in the overall region of the vector operations for the solution of linear equations, there can be obtained a degree of parallelization almost identical to the order n of the matrix A (n=n.sub.x three-dimensional matrix and n=n.sub.x two-dimensional matrix).
As the preconditioning for solution of conjugate gradient series, although the processing procedure can be established to be suitable for vector processors according to the incomplete LU factorization, it is difficult to set the processing to be appropriate for the super-parallel processing. According to the second aspect of the present invention, the preconditioning matrix is structured with products resulted from multiplications between (I-Ai), i=1, 2, . . . , m, thereby implementing a calculation method favorably applicable to a computer having a plurality of vector processors and a super-parallel computer. Moreover, by configuring the preconditioning matrix with the results from multiplications between (I-Ai), i=1, 2, . . . , m, as compared with the conventional case where a formula E=A.sub.1 +A.sub.2 + . . . +Am is adopted to establish a formula I-E+E.sup.2 -E.sup.3 +E.sup.4 . . . , the convergence of solution can be improved for the gradient series. In addition, as technological means for stabilizing convergence of solution of conjugate gradient series, there is adopted a method of scaling the matrix A and the right-side vector b according to each diagonal element and the sum of absolute values of associated nondiagonal elements. Resultantly, even when the diagonal element superiority of the coefficient matrix A is remarkable deteriorated, it is possible to obtain converged numerical solutions for the linear equations in a stable condition.
In a step 1 of FIG. 1, a coefficient matrix A of the linear equations Ax=b generated in accordance with the finite element method and a right-side vector b thereof are written in a storage. For the coefficient matrix A, a diagonal matrix D and a nondiagonal matrix A are separatedly memorized. Moreover, for the nondiagonal matrix A, only the nonzero elements are to be stored. Consequently, for the nonzero elements of each row, column number index values are stored pairwise in a column number table L. In FIG. 1, the dimensionality or order of the matrix is indicated as N and the maximum number of nonzero elements per row excepting the diagonal element is denoted as ND. In a step 2, there are computed scaling values respectively for scaling the coefficient matrix and the right-side vector b. Assume that each of the diagonal elements D(i), i=1, . . . , N is positive. In a case where 1/D(i), I=1, . . . , N is used in the scaling, when the condition of the diagonal element superiority (D(i)&lt;&lt;U(i)) is remarkably deteriorated, the convergence of solution is impossible. To overcome this difficulty, there is adopted a method in which a scaling value W(i) for each row is calculated according to the sum μ.sub.i (i=1, . . . , N) of absolute values of nondiagonal elements of the row and the absolute value of the diagonal element D(i) (i=1, . . . , N). In general, a parameter α for the convergence of solution need only be set to a fixed value of about 4 However, there may take place a case where the convergence cannot be realized under the conditions above. To cope with such a disadvantageous situation, the system is so configured to be capable of changing the value of α. In a step 3, the scaling is accomplished on the coefficient matrix and the right-side vector. Namely, the value wi (i=1, . . . , N) obtained in the step 2 is multiplied by the pertinent elements thereof. In a step 4, the elements of the coefficient matrix are sorted according to the value of i. The sorting is achieved in a descending order thereof in this case. The scaling and sorting steps may be reversed. In a step 5, using the sorted elements, m submatrices E1, . . . , Em (m is determined according to the value of ND; m≦ND) are produced. The operation above will be described in more detail later with reference to FIG. 2. In a step 6, a sequence of products w.sub.1 to w.sub.m are generated from the series of submatrices E1, . . . , Em. The steps above are implemented by means which executes the calculations and processing above while referencing the data written in a storage.
FIG. 2 shows a specific method of subdividing the matrix including nondiagonal nonzero elements created from the nondiagonal nonzero element matrix A into m submatrices. A reference numeral 7 denotes a method of subdivision when the number of maximum nonzero elements per row takes a large value. Since the matrices are sorted according to the value of j as . , n; j=1, . . . , ND-1), the subdivision is conducted such that the resultant submatrix includes an element of the row when the value of j is small, whereas the resultant submatrix includes a larger number of elements as the value of j becomes to be greater. A reference numeral 8 designates a method of subdivision when the number of maximum nonzero elements per row takes a small value.
In this connection, although FIG. 2 shows an example of subdivision. In general, the grouping of submatrices need only conducted such that value of the element of elements thereof takes substantially an identical value, which therefore can be processed by the computer.
FIG. 3 shows a calculation procedure in which a vector as a solution of simultaneous linear equations A is obtained through iterative calculations by use of the Bi-CGSTAB with preconditioning (1990, similar to the solution of Van der Vorst) after the steps of FIG. 1.
In a step 10, the data items are prepared for the iterative calculations. A vector x is an initial vector. If the elements thereof is not determined, zeros need only be set to the respective elements. A vector r is a residual vector. Moreover, (r, r) indicates an inner product. This representation applies to the following description. In a step 11, the iterative calculations are controlled. In a step 12, the iterative calculations are executed according to the CGPM with preconditioning. The solutions are obtained as vector x. In the formulae, A indicates a matrix and vectors p, q, r, r.sub.0, e, and v denote vectors of order N. The other symbols designate scalars. A step 12 is a known technology and hence will not be described. The steps above are achieved by means which executes the calculations and processing by referencing the data memorized in the storage.
FIG. 6 shows an example of a method of storing nondiagonal nonzero elements of the coefficient matrix of simultaneous linear equations generated according to the finite element division of FIG. 5. A reference numeral 20 indicates a column number table L(N,ND) of nonzero elements. A numeral 21 stands for a nonzero element matrix A(N,ND). For j=l(i,k), A(i,j) indicates an element a.sub.i,j of the dense matrix. A numeral 22 is a column number index. When this entry is open or empty, it is indicated that the associated nonzero element is missing. A numeral 23 denotes a nonzero element of the matrix. A numeral 24 designates an element which has a storage area and which has a value of zero. Based on the nonzero element matrix A(N,ND) of this type, there are created submatrices E1, E2, . . . , Em shown in FIG. 1.
In a step 31 of FIG. 7, a coefficient matrix of the simultaneous linear equations generated according to the difference calculus and the right-side vector thereof are memorized in a storage. For the coefficient matrix A, there are separatedly stored a diagonal matrix D and a nondiagonal matrix A. In this example, the discretization is achieved according to the three-dimensional seven-point difference calculus. When the two-dimensional five-point difference calculus is employed, the band matrix including nondiagonal nonzero elements is represented as A(N,4). When there exists a periodic boundary condition, the number of submatrices for the nondiagonal nonzero matrix is increased by two or four. The order of the linear system is N. In a step 32, there are calculated values for scaling the coefficient matrix and the right-side vector. Assume that each of the diagonal elements D(i), i=1, . . . , N is positive. In the conventional case where 1/D(i), i=1, . . . , N is used for the scaling, when the diagonal element superiority is remarkably deteriorated, there cannot be attained the convergence of solution. To overcome this difficulty, there is adopted the following method. The computation is achieved, for each row, according to the sum μi (i=1, . . . , N) of absolute values of nondiagonal elements and the absolute value of the associated diagonal element D(i) (i=1, . . . , N). The parameter α need only be set to about 4.0 in general. However, there may occur a case where the converged solution cannot be obtained. To cope with such a disadvantageous situation, the system is so constructed to be capable of varying the value of α. In a step 33, the coefficient matrix and the right-side vector are scaled, namely, the values of w.sub.i obtained in the step 32 are multiplied by the associated elements thereof. In a step 34, the nondiagonal elements of the matrix are grouped into m submatrices A1, A2, . . . , Am. In this case using the three-dimensional seven-point difference calculus, the matrix is split into six submatrices A1, A2, . . . , A6. In a step 35, a preconditioning matrix M is produced from the submatrices A1, A2, . . . , A6. The respective, steps above can be implemented by means which executes the calculations and processing above by referencing the data written in a storage.
In this embodiment, in order to more suitably apply the calculation to the parallel vector computer and the super-parallel computer, the incomplete LU factorization is not employed,. namely, there is used a matrix including products resultant from multiplications between (I-Ai), i=1, 2, . . . , m. When the incomplete LU factorization is utilized, the degree of parallelization is remarkably increased as compared with the order N of the linear system. In contrast thereto, according to this method, the parallelization degree is kept to be identical to the order N. Moreover, the provision of the products resultant from multiplications between (I-Ai), i=1, 2, . . . , m improves the characteristic of convergence of solution of conjugate gradient series when compared with the case where E=A.sub.1 +A.sub.2 + . . . +Am is assumed to establish I-E+E.sup.2 -E.sup.3 +E.sup.4 . . . . This leads to a convergence speed substantially equal to that developed when the incomplete LU factorization is used.
In a step 51 of FIG. 10, there is shown an example of a preparative operation for conducting an incomplete LU factorization on the coefficient matrix A. Namely, the sum μi of absolute values of nondiagonal elements is computed for each row. There is also calculated a value wi to be assumed as a diagonal element in the incomplete LU factorization. In the formulae, N stands for the dimensionality of the matrix and the symbols other than μi and wi are associated with those shown in FIG. 11. Symbols a.sub.i, b.sub.i, c.sub.i, e.sub.i, f.sub.i, and g.sub.i denotes nondiagonal elements. The value of di is set to be greater than zero (di&gt;0). In a step 52, there is conducted an incomplete LU factorization corrected according to the correction proposed by Gustaffson. In this computation, d.sub.i =1/{wi- . . . } is employed in place of the conventional formula d.sub.i =1/{di- . . . }. Resultantly, even when the coefficient matrix is ill conditioned (for a diagonal element, the sum of absolute values of associated nondiagonal is greater than the absolute value of the diagonal element), the convergence of solution is stabilized. Moreover, regardless of the ill-conditioned matrix, the value of the correction coefficient α can be fixed to about 0.95. In addition, to increase the convergence speed, the value of α need only be increased as compared with the dimensionality or order N, where α is less than one. Furthermore, a.sub.i and g.sub.i, b.sub.i and f.sub.i, and c.sub.i and e.sub.i are arranged at positions apart from the diagonal positions by m, one, and one, respectively. When a vector computer is used for the computation, the calculation of the step 52 need not be achieved in the order of i=1, 2, 3, . . . , N. It is only necessary to order the items in a direction according to the hyper-plane method. This technology has already been broadly known.
A reference numeral 53 of FIG. 11 denotes the configuration indicating positions of nonzero elements of the original coefficient matrix A. In this graph, a letter d stands for a diagonal matrix, letters a, b, c, e, f, and g designate non diagonal matrices, and letters a.sub.i, b.sub.i, c.sub.i, d.sub.i, e.sub.i, f.sub.i, and g.sub.i indicate elements of row i in the respective matrices. A graph 54 shows positional configuration of nonzero elements of the lower triangular matrix L attained from the incomplete LU factorization, a graph 55 presents the positional structure of diagonal matrix D, and a graph 56 indicates a positional constitution of nonzero elements of the upper triangular matrix U. In these graphs, each of the symbols a, b, etc. indicate a matrix of the same value as the associated matrix shown in the graph 53 or 54. Only the value of d is additionally calculated.
Moreover, q=[LCD].sup.-1 multiply an inverse matrix of the LDU matrix by the vector w. Namely, the known forward and back substitutions are used to compute the vector 9 from the vector w. Letters A, L, D, and U denote matrices having an order N. Vectors b, x, p, q, r, r.sub.0, e, and v stand for vectors of order N. Other symbols indicates scalars.
FIG. 13 is a flowchart showing the operation of selecting a preconditioning method in which submatrices are generated for KEY=0 and the incomplete LU factorization (LDU) is employed as the preconditioning for KEY=1. In a step 61, S is set to the maximum value of the ratio between the value of a diagonal element di and the sum of absolute values of nondiagonal elements associated therewith. If S takes a small value, the property of the matrix is satisfactory; otherwise, the matrix is ill conditioned. In a decision step 62, when the coefficient matrix A is completely a diagonal element superior matrix in the non-stationary computation or the like, namely, for S≦1-ε.sub.1, it is decided to set 0 to KEY (KEY=0). In general, ε.sub.1 is set to about 0.1. In a step 63, when the diagonal element superiority of the coefficient matrix A is remarkably deteriorated, namely, for S≧ε.sub.2, it is decided to set one to KEY (KEY=1). In general, ε.sub.2 is set to about two. In a step 64, it is judged, when the coefficient matrix A is found to be not particularly satisfactory or unsatisfactory, to determine whether or not a plurality of vector processors can be adopted for the computation. If this is the case, KEY is set to 0. If only one vector processor is available, KEY is set to one. For KEY=0, there is selected a preconditioning method suitable for the plural vector processors. Namely, the vector processors develops a highly efficient operation.
FIG. 14 is a flowchart showing the procedure of selecting one of the preconditioning methods to conduct iterative calculations, thereby obtaining vector x as solutions of the linear equations according to the CGPM with preconditioning. In a step 67, the value of KEY is established. In a step 68, a preconditioning is executed depending on the value (0 or 1) of KEY. For KEY=0, the preprocessing matrix M is generated according to the procedure of FIG. 7. In a step 69, the residual vector r is established also depending on the value of KEY. In a step 70, a preparative operation is conducted for the iterative calculations. In a step 71, the iterative calculations are controlled. Through steps 72 to 75, the iterative calculations are achieved in accordance with the CGPM with preconditioning so as to obtain solutions in the form of the vector x. Each of the steps 72 and 74 conducts a computation depending on the value of KEY. The steps 23 and 25 carry out common calculations. Letters A, M, L, D, and U denote matrices of an order N; vectors b, x, p, q, r, r.sub.0, e, and v have an order N, and other symbols stand for scalars.
According to the embodiment, using the iterative solution of conjugate gradient series with incomplete LU factorization, there is obtained an advantage of a stable computation of numerical solutions for simultaneous linear equations. Particularly, it is possible to avoid the conventional case in which when the diagonal superiority is greatly deteriorated for the matrix, the converged solution cannot be attained according to the conventional incomplete LU factorization. Moreover, by setting the correction coefficient α of the Gustafsson-type correction is fixed to be about 0.95 regardless of the property of diagonal element superiority of the matrix, the characteristic of convergence can be improved to be three to five times, as compared with the conventional case, for a two-dimensional problem of 100 by 100 subdivision. Furthermore, when the value of α is increased in proportion to the subdivision number used to subdivide the pertinent area (α&lt;1.0), the convergence speed can be much more increased.
Patentcitaties Geciteerd patent Aanvraagdatum Publicatiedatum Aanvrager TitelUS469724714 juli 198629 sept 1987Hughes Aircraft CompanyMethod of performing matrix by matrix multiplicationUS47870574 juni 198622 nov 1988General Electric CompanyFinite element analysis method using multiprocessor for matrix manipulations with special handling of diagonal elementsUS530134220 dec 19905 april 1994Intel CorporationParallel processing computer for solving dense systems of linear equations by factoring rows, columns, and diagonal, inverting the diagonal, forward eliminating, and back substitutingNiet-patentcitatiesReferentie1Bratkovic, "Improved Numerical Stability of Sparse Matrix Reduction Method," IEEE International Symposium on Circuits and Systems, pp. 631-634. Aug. 1988.2Bratkovic, Improved Numerical Stability of Sparse Matrix Reduction Method, IEEE International Symposium on Circuits and Systems, pp. 631 634. Aug. 1988.3Chen et al., "Parallel LU Factorization for Circuit Simulation on a MIMD Computer," International Conference on Computer Design, pp. 129-132. May 1988.4Chen et al., Parallel LU Factorization for Circuit Simulation on a MIMD Computer, International Conference on Computer Design, pp. 129 132. May 1988.5Gustafsson, "A Class of First Order Factorization Methods," BIT 18 (1978), pp. 142-156.6Gustafsson, A Class of First Order Factorization Methods, BIT 18 (1978), pp. 142 156.7Ma et al., "2 Iterative Methods . . . 3 Vectorization and Parallelization," vol. 4, Winter 1990, pp. 12-24.8Ma et al., 2 Iterative Methods . . . 3 Vectorization and Parallelization, vol. 4, Winter 1990, pp. 12 24.9Van Der Vorst, "B1-CGSTAB: A First and Smoothly Converging Variant of BI-CG for the Solution of Nonsymmetric Linear Systems," pp. 1-16 - Could Not Be Considered Due to Lack of Publishing Date.10Van Der Vorst, "ICCG and Related Methods for 3D Problems on Vector Computers," Comp. Phys. Communications, 53 (1989), pp. 223-235.11Van Der Vorst, B1 CGSTAB: A First and Smoothly Converging Variant of BI CG for the Solution of Nonsymmetric Linear Systems, pp. 1 16 Could Not Be Considered Due to Lack of Publishing Date.12Van Der Vorst, ICCG and Related Methods for 3D Problems on Vector Computers, Comp. Phys. Communications, 53 (1989), pp. 223 235. Verwijzingen naar dit patent Citerend patent Aanvraagdatum Publicatiedatum Aanvrager TitelUS584482129 april 19971 dec 1998Lucent Technologies Inc.Systems and methods for determining characteristics of a singular circuitUS588718629 maart 199523 maart 1999Fujitsu LimitedMethod of solving simultaneous linear equations in a memory-distributed parallel computerUS607893829 mei 199620 juni 2000Motorola, Inc.Method and system for solving linear systemsUS615471629 juli 199828 nov 2000Lucent Technologies - Inc.System and method for simulating electronic circuitsUS618227020 nov 199730 jan 2001Lucent Technologies Inc.Low-displacement rank preconditioners for simplified non-linear analysis of circuits and other devicesUS636019025 nov 199819 maart 2002Nec CorporationSemiconductor process device simulation method and storage medium storing simulation programUS679919426 juni 200128 sept 2004Fujitsu LimitedProcessing apparatus for performing preconditioning process through multilevel block incomplete factorizationUS681037014 maart 200026 okt 2004Exxonmobil Upstream Research CompanyMethod for simulation characteristic of a physical systemUS682658519 okt 200130 nov 2004Hitachi Software Engineering Co., Ltd.Method and apparatus for solving simultaneous linear equationsUS690751320 maart 200114 juni 2005Fujitsu LimitedMatrix processing method of shared-memory scalar parallel-processing computer and recording mediumUS694125529 juni 20016 sept 2005Object Reservoir, Inc.Feature modeling in a finite element modelUS700695129 juni 200128 feb 2006Object Reservoir, Inc.Method for solving finite element models using time slabbingUS702796429 juni 200111 april 2006Object Reservoir, Inc.Method and system for solving finite element models using multi-phase physicsUS704341329 juni 20019 mei 2006Object Reservoir, Inc.Method for modeling an arbitrary well path in a hydrocarbon reservoir using adaptive meshingUS70891592 april 20018 aug 2006Nec Electronics CorporationMethod and apparatus for matrix reordering and electronic circuit simulationUS714967129 juni 200112 dec 2006Object Reservoir, Inc.Method and system for coordinate transformation to model radial flow near a singularityUS726050829 juni 200121 aug 2007Object Reservoir, Inc.Method and system for high-resolution modeling of a well bore in a hydrocarbon reservoirUS732819520 nov 20025 feb 2008Ftl Systems, Inc.Semi-automatic generation of behavior models continuous value using iterative probing of a device or existing component modelUS736997322 juli 20056 mei 2008Object Reservoir, Inc.Method and system for representing reservoir systemsUS741837031 maart 200426 aug 2008International Business Machines CorporationMethod, apparatus and computer program providing broadband preconditioning based on reduced coupling for numerical solversUS748393724 okt 200327 jan 2009Fujitsu LimitedParallel processing method for inverse matrix for shared memory type scalar parallel computerUS753960210 jan 200626 mei 2009Ftl Systems, Inc.Accelerating simulation of differential equation systems having continuous behaviorUS767281813 april 20052 maart 2010Exxonmobil Upstream Research CompanyMethod for solving implicit reservoir simulation matrix equationUS793375115 aug 200826 april 2011International Business Machines CorporationMethod, apparatus and computer program providing broadband preconditioning based on reduced coupling for numerical solversUS793375215 aug 200826 april 2011International Business Machines CorporationMethod, apparatus and computer program providing broadband preconditioning based on a reduced coupling for numerical solversUS828552927 feb 20099 okt 2012Fujitsu LimitedHigh-speed operation method for coupled equations based on finite element method and boundary element methodUS830679824 dec 20086 nov 2012Intel CorporationFluid dynamics simulatorUS2010010676222 dec 200929 april 2010Fujitsu LimitedComputer apparatus and calculation methodUS2010016170224 dec 200824 juni 2010Intel CorporationFluid Dynamics SimulatorUS201100104097 juli 200913 jan 2011L3 Communications Integrated Systems, L.P.System for conjugate gradient linear iterative solversUS2012017944026 maart 201212 juli 2012International Business Machines CorporationCombined matrix-vector and matrix transpose vector multiply for a block-sparse matrixEP0919939A227 nov 19982 juni 1999Nec CorporationSemiconductor process device simulation method and storage medium storing simulation programEP0999581A226 okt 199910 mei 2000Nec CorporationSimulation method executable with less timeDraaienOriginele afbeeldingGoogle Startpagina - Sitemap - USPTO-bulkdownloads - Privacybeleid - Servicevoorwaarden - Over Google Patenten - Feedback verzendenGegevens geleverd door IFI CLAIMS Patent Services© 2012 Google