Determining the equivalence of two sets of simultaneous linear algebraic equations

• US 7,836,112 B2
• Filed: 09/20/2005
• Issued: 11/16/2010
• Est. Priority Date: 06/20/2000
• Status: Expired due to Fees

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Bera, Rajendra Kumar
• Primary Examiner(s): Do; Chat C
• Application Number:
  US11/231,091
• Publication Number:
  US 20060015550A1
• Time in Patent Office: 1,883 Days
• Field of Search: 708200-209, 708/490, 708/495, 708/523, 708/160
• US Class Current: 708/200
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations

Abstract

A computer implemented method (200) is described for determining the equivalence of two sets of simultaneous linear algebraic equations. Each of said equations is of a form:
e_i1x₁+e_i2x₂+e_i3x₃+ . . . +e_iix_n=b_i
wherein x_j are unknowns, e_ij are coefficients and b_i are quantities, and defining the relationship between the unknowns within the set. The coefficients and quantities are known algebraic expressions. The unknowns are iteratively eliminated (250 to 280) from each of the sets of simultaneous linear algebraic equations until each of said equations are in the form:
(l_ii)_kx_i=(r_i)_k
wherein l_ii and r_i are algebraic expressions, and k={1;2} indicate one of said sets that said equation is derived from. The products (l_ii)₁*(r_i)₂ and (l_ii)₂*(r_i)₁ are compared (300) for each of the unknowns. Only if the products match (310) for all the unknowns are the two sets of simultaneous linear algebraic equations equivalent (312). An apparatus (100) for performing the above method (200) is also provided.

Claims

1. A computer implemented method in a simulation of a physical system, wherein the system is described by a first set of n simultaneous linear algebraic equations and is simulated by a second system described by a second set of n simultaneous linear algebraic equations, each of said equations being of a form:

e_i1x₁+e_i2x₂+e_i3x₃+ . . . +e_inx_n=b_i

wherein x_j are n unknowns, e_ij are n coefficients for each of the n equations of each set, and b_i are n quantities, said coefficients and quantities being known algebraic expressions, said method comprising the steps of;

a) providing respective reduced sets, wherein step a) includes the following substeps for each of the equations of each of the sets;

a1) arranging variables in the coefficients e_ij and the quantities b_i as multiplied instances of the variables;

a2) arranging expressions resulting from substep a1) into a form <

unitaryoperation>

<

operand>

<

operator>

<

operand>

. . . <

operator>

<

operand>

, wherein the unitary operation is either + or −

, and each operator is one of;

+, −

, or *, and wherein the substep a2) includes inserting the unitary operation in front of an expression if the expression does not already commence with the unitary operator;

a3) eliminating terms resulting from substep a2);

a4) substituting, in expressions resulting from substep a3), all + operators with a string +1* and all −

operators with a string −

1*;

a5) converting numerical terms resulting from substep a4) into an exponential format; and

a6) sorting operands of terms resulting from substep a5); and

b) combining and rearranging terms resulting from substeps a1) through a6) to eliminate said unknowns from each of said sets of simultaneous linear algebraic equations and to provide for each set, n equations in a form;

(l_ii)_kx_i=(r_i)_k

wherein l_ii and r_i are algebraic expressions, i={1 through n}, k=1 indicates the first one of said sets and k=2 indicates the second one of said sets; and

c) comparing, using a processor, for each of said unknowns, a first product (l_ii)₁*(r_i)₂ and a second product (l_ii)₂*(r_i)₁, wherein the first product is an algebraic expression and the second product is an algebraic expression, and wherein if said products match for all said unknowns said second set of simultaneous linear algebraic equations is equivalent to the first set of simultaneous linear algebraic equations and thereby is determined to be a proper representation of the physical system, wherein the eliminating said unknowns in step a) enables the comparing in step c) to determine if the products match without determining numerical values for the unknowns and without performing a matrix inversion.

2. The computer implemented method according to claim 1, wherein certain variables in the coefficients e_ij and the quantities b_i of such an equation are raised to a positive integer power, and wherein in a1) each instance of such a variable is raised to a power of 1.

3. The method according to claim 1, wherein a3) includes:

multiplying terms inside and outside brackets to render certain ones of the brackets superfluous; and

discarding the superfluous brackets.

4. The method according to claim 1, wherein in a5) the exponential format includes, [unsigned number]e[e-sign] [unsigned exponent], wherein e[e-sign] [unsigned exponent] for a numerical term represents a quantity 10 raised to a power [e-sign] [unsigned exponent] multiplied by a number represented by, [unsigned number], such that, [unsigned number]e[e-sign] [unsigned exponent] equals the numerical term, [unsigned number] being an n-digited number comprising only digits, n being a prefixed integer greater than 0, [e-sign] being a sign of the exponent, [unsigned exponent] being an m-digited number, and m being a prefixed integer greater than 0.

5. The method according to claim 1, wherein in a6) the sorting of the operands arranges the operands into ascending order according to a certain standardized value sequence.

6. The method according to claim 1, wherein in b) the combining of such terms includes combining ones of the terms having matching variable-groups into a single term.

7. The method according to claim 6, wherein in b) the rearranging of such terms includes arranging ones of the terms into an ascending order according to values of their respective variable-groups.

8. An apparatus comprising:

a processor;

a storage device connected to the processor, wherein the storage device has computer readable program code for controlling the processor, and wherein the processor is operative with the program code for simulating a physical system, wherein the system is described by a first set of n simultaneous linear algebraic equations and is simulated by a second system described by a second set of n simultaneous linear algebraic equations, each of said equations being of a form;

e_i1x₁+e_i2x₂+e_i3x₃+ . . . +e_inx_n=b_i

wherein x_j are n unknowns, e_ij are n coefficients for each of the n equations of each set, and b_i are n quantities, said coefficients and quantities being known algebraic expressions, the program code comprising;

instructions for performing a step a) of providing respective reduced sets, wherein the instructions include;

instructions for performing a substep a1) of arranging variables in the coefficients e_ij and the quantities b_i in a form having multiplied instances of the variables;

instructions for performing a substep a2) of arranging expressions resulting from substep a1) into a form <

unitaryoperation>

<

operand>

<

operator>

<

operand>

. . . <

operator>

<

operand>

, wherein the unitary operation is either + or −

, and each operator is one of;

+, −

, or *, and wherein the substep a2) includes inserting the unitary operation in front of an expression if the expression does not already commence with the unitary operator;

instructions for performing a substep a3) of eliminating terms resulting from substep a2);

instructions for performing a substep a4) of substituting, in expressions resulting from substep a3), all + operators with a string +1* and all −

operators with a string −

1*;

instructions for performing a substep a4) of substituting, in expressions resulting from substep a3), all + operators with a string +1* and all −

operators with a string −

1*;

instructions for performing a substep a5) of converting numerical terms resulting from substep a4) into an exponential format; and

instructions for performing a substep a6) of sorting operands of terms resulting from substep a5); and

instructions for performing a step b) of combining and rearranging terms resulting from substeps a1) through a6) to eliminate said unknowns from each of said sets of simultaneous linear algebraic equations and to provide for each set, n equations in a form;

(l_ii)_kx_i=(r_i)_k

wherein l_ii and r_i are algebraic expressions, i={1 through n}, and k=1 indicates the first one of said sets and k=2 indicates the second one of said sets; and

instructions for performing a step c) of comparing, for each of said unknowns, a first product (l_ii)₁*(r_i)₂ and a second product (l_ii)₂*(r_i)₁, wherein the first product is an algebraic expression and the second product is an algebraic expression, and wherein if said products match for all said unknowns said second set of simultaneous linear algebraic equations is equivalent to the first set of simultaneous linear algebraic equations and thereby is determined to be a proper representation of the physical system, wherein the eliminating said unknowns in step a) enables the comparing in step c) to determine if the products match without determining numerical values for the unknowns and without performing a matrix inversion.

9. The apparatus according to claim 8, wherein certain variables in the coefficients e_ij and the quantities b_i of such an equation are raised to a positive integer power, and wherein in a1) each instance of such a variable is raised to a power of 1.

10. The apparatus according to claim 8, wherein a3) includes:

multiplying terms inside and outside brackets to render certain ones of the brackets superfluous; and

discarding the superfluous brackets.

11. The apparatus according to claim 8, wherein in a5) the exponential format includes, [unsigned number]e[e-sign] [unsigned exponent], wherein e[e-sign] [unsigned exponent] for a numerical term represents a quantity 10 raised to a power [e-sign] [unsigned exponent] multiplied by a number represented by, [unsigned number], such that, [unsigned number]e[e-sign] [unsigned exponent] equals the numerical term, [unsigned number] being an n-digited number comprising only digits, n being a prefixed integer greater than 0, [e-sign] being a sign of the exponent, [unsigned exponent] being an m-digited number, and m being a prefixed integer greater than 0.

12. The apparatus according to claim 8, wherein in a6) the sorting of the operands arranges the operands into ascending order according to a certain standardized value sequence.

13. The apparatus according to claim 8, wherein in b) the combining of such terms includes combining ones of the terms having matching variable-groups into a single term, and in b) the rearranging of such terms includes arranging ones of the terms into an ascending order according to values of their respective variable-groups.

14. A computer program product for use in a simulation of a physical system, wherein the system is described by a first set of n simultaneous linear algebraic equations and is simulated by a second system described by a second set of n simultaneous linear algebraic equations, each of said equations being of a form:

e_i1x₁+e_i2x₂+e_i3x₃+ . . . +e_inx_n=b_i

wherein x_j are n unknowns, e_ij are n coefficients for each of the n equations of each set, and b_i are n quantities, said coefficients and quantities being known algebraic expressions, the computer program product residing on a computer readable storage medium having computer readable program code, the program code comprising;

instructions for performing a step a) of providing respective reduced sets, wherein the instructions include;

instructions for performing a substep a1) of arranging variables in the coefficients e_ij and the quantities b_i in a form having multiplied instances of the variables;

instructions for performing a substep a1) of arranging variables in the coefficients e_ij and the quantities b_i in a form having multiplied instances of the variables;

instructions for performing a substep a2) of arranging expressions resulting from substep a1) into a form <

unitaryoperation>

<

operand>

<

operator>

<

operand>

. . . <

operator>

<

operand>

wherein the unitary operation is either + or −

, and each operator is one of;

+, −

, or *, and wherein the substep a2) includes inserting the unitary operation in front of an expression if the expression does not already commence with the unitary operator;

instructions for performing a substep a3) of eliminating terms resulting from substep a2);

instructions for performing a substep a4) of substituting, in expressions resulting from substep a3), all + operators with a string +1* and all −

operators with a string −

1*;

instructions for performing a substep a5) of converting numerical terms resulting from substep a4) into an exponential format; and

instructions for performing a substep a6) of sorting operands of terms resulting from substep a5); and

instructions for performing a step b) of combining and rearranging terms resulting from substeps a1) through a6) to eliminate said unknowns from each of said sets of simultaneous linear algebraic equations and to provide for each set, n equations in a form;

(l_ii)_kx_i=(r_i)_k

wherein (l_ii) and r_i are algebraic expressions, i={1 through n}, k=1 indicates the first one of said sets and k=2 indicates the second one of said sets; and

instructions for performing a step c) of comparing, using a processor, for each of said unknowns, a first product (l_ii)₁*(r_i)₂ and a second product (l_ii)₂*(r_i)₁, wherein the first product is an algebraic expression and the second product is an algebraic expression, and wherein if said products match for all said unknowns said second set of simultaneous linear algebraic equations is equivalent to the first set of simultaneous linear algebraic equations and thereby is determined to be a proper representation of the physical system, wherein the eliminating said unknowns in step a) enables the comparing in step c) to determine if the products match without determining numerical values for the unknowns and without performing a matrix inversion.

15. The computer program product according to claim 14, wherein certain variables in the coefficients e_ij and the quantities b_i of such an equation are raised to a positive integer power, and wherein in a1) each instance of such a variable is raised to a power of 1.

16. The computer program product according to claim 14, wherein a3) includes:

multiplying terms inside and outside brackets to render certain ones of the brackets superfluous; and

discarding the superfluous brackets.

17. The computer program product according to claim 14, wherein in a5) the exponential format includes, [unsigned number]e[e-sign] [unsigned exponent], wherein e[e-sign] [unsigned exponent] for a numerical term represents a quantity 10 raised to a power [e-sign] [unsigned exponent] multiplied by a number represented by, [unsigned number], such that, [unsigned number]e[e-sign] [unsigned exponent] equals the numerical term, [unsigned number] being an n-digited number comprising only digits, n being a prefixed integer greater than 0, [e-sign] being a sign of the exponent, [unsigned exponent] being an m-digited number, and m being a prefixed integer greater than 0.

18. The computer program product according to claim 14, wherein in a6) the sorting of the operands arranges the operands into ascending order according to a certain standardized value sequence.

19. The computer program product according to claim 14, wherein in b) the combining of such terms includes combining ones of the terms having matching variable-groups into a single term.

20. The computer program product according to claim 14, wherein in b) the rearranging of such terms includes arranging ones of the terms into an ascending order according to values of their respective variable-groups.