Method, apparatus, and computer program product for solving an equation system using pure spreadsheet functions

• US 10,114,812 B1
• Filed: 01/04/2018
• Issued: 10/30/2018
• Est. Priority Date: 01/03/2015
• Status: Active Grant

• Current Assignee: Chahid Kamel Ghaddar
• Original Assignee: Chahid Kamel Ghaddar
• Inventors: Ghaddar, Chahid Kamel
• Primary Examiner(s): Baderman, Scott T
• Assistant Examiner(s): Lee, Sookil J
• Application Number:
  US15/861,897
• Time in Patent Office: 299 Days
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174

Abstract

The present disclosure provides a method, an apparatus, and a computer program product to interact with a programming interface of a spreadsheet software application for computing the value of a formula that depends explicitly or implicitly on one or more cells designated as variables for the formula, based on supplied values for the variables, and without modifying any values or content of the spreadsheet software application. In a first utility, the method is utilized in pure solver functions of the spreadsheet application for computing numerical solution of an equation system modeled by at least one or more formulas and variables in the spreadsheet software application. In a second utility, the method is utilized in an optimization process executed by pure solver functions of the spreadsheet application for computing optimal parameters for a parameterized equation system modeled by at least one or more formulas, variables, and parameters.

Claims

1. A method for computing a value of a root formula expression stored in a spreadsheet software application, the method comprising:

A) displaying and operating one or more tabular datasheets by executing the spreadsheet software application on a computer device, each tabular datasheet having a plurality of cells each being designated with a column identifier and a row identifier, the cells being configured to receive values or formula expressions input, evaluate formula expressions, and display output; and

B) providing a programming interface to the spreadsheet software application, the programming interface being configured to;

B1) receive the identifiers for at least one of the cells and retrieve a value or a formula expression from the one of the cells;

B2) receive at least an evaluable formula expression, and evaluate its equivalent value, wherein the evaluable formula expression represents an independent textual expression that is evaluated to an equivalent numerical value by said programming interface; and

C) providing a graph constructor algorithm for representing the root formula and its interdependence on an additional nested formulas and the variables on a tree-structured graph of relational nodes, the graph constructor algorithm comprising;

C1) receiving the identifiers for the root formula'"'"'s cell and the variables'"'"' cells and communicating with said programming interface to retrieve the root formula expression;

C2) identifying and retrieving the expressions for the additional nested formulas expressions on which the root formula depends by traversing the dependency of any retrieved expression on additional formulas;

C3) constructing a tree-structured graph of relational nodes for representing the interdependence of the root formula expression on the additional nested formulas expressions and the variables;

C4) transforming the tree-structured graph into an evaluation graph of relational nodes containing an equivalent sequence of formula expressions; and

D) providing a graph evaluator algorithm for evaluating said evaluation graph, the graph evaluator algorithm comprising;

D1) receiving said evaluation graph and a supply of values for the variables;

D2) traversing the relational nodes of said evaluation graph in an order of their interdependence and transforming the formula expression in each relational node into an evaluable formula expression by replacing the variables in said formula expression in the relational node by the supplied values of the variables, and any reference to a traversed child relational node;

D3) obtaining a value of the relational node by evaluating the value of the evaluable formula expression in the relational node via said programming interface;

D4) aggregating the obtained values of the relational nodes in an order of their interdependence to obtain the value of the root formula expression; and

E) providing a computer software application communicable with the spreadsheet software application via said programming interface, the computer software application being configured to execute said graph constructor algorithm followed by said graph evaluator algorithm obtaining the value of the root formula expression in accordance with the supplied values of the one or more variables for the root formula, the root formula depending on the variables explicitly or implicitly through interdependence on the additional nested formulas, not storing or modifying any stored values in the spreadsheet application.

2. The method of claim 1, wherein the spreadsheet software application comprises a native spreadsheet software application.

3. The method of claim 1, wherein the spreadsheet software application comprises a web-based spreadsheet software application.

4. The method of claim 1, further comprising utilizing a solver function of said spreadsheet software application for computing and displaying a numerical solution to an equation system represented by one or more root formulas in a first group of the cells, one or more variables of said root formulas in a second group of the cells, and zero or more parameters of the equation system;

and wherein the solver function using the graph evaluator in conjunction with an underlining algorithm for computing the solution to the equation system, and having one or more first input arguments, receives at least the identifiers for the first and second groups of the cells; and

wherein evaluating a formula expression of the solver function in a third group of the cells, computes and displays the numerical solution to the equation system in the third group of the cells.

5. The method of claim 4, wherein the solver function is a pure function.

6. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution value of an integral of said one or more root formulas.

7. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution value of a multiple integral of said one or more root formulas comprising recursively computing nested integrals of said one or more root formulas.

8. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution value of a derivative of said one or more root formulas.

9. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution value of a mixed partial derivative of said one or more root formulas comprising recursively computing nested derivatives of said one or more root formulas.

10. The method of claim 4, wherein the equation system comprises differential equations.

11. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to an ordinary differential-algebraic equations system.

12. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to an initial value ordinary differential-algebraic equations system comprising receiving initial values from the variables in the second group of the cells.

13. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to a boundary value ordinary differential-algebraic equations system comprising:

receiving boundary points values and corresponding boundary conditions formulas from an additional group of the cells; and

utilizing the graph evaluator to evaluate said boundary conditions formulas in accordance with the underlining algorithm.

14. The method of claim 11, wherein displaying the solution comprises displaying values of the solution in a tabular array of the datasheet;

wherein values of the equations system'"'"'s independent variable are listed in a first column of the tabular array; and

wherein corresponding values of the equations system'"'"'s dependent variables are listed in subsequent columns of the tabular array; and

wherein corresponding labels for the equations system'"'"'s variables are displayed for each of the columns in the first row of the tabular array; and

wherein corresponding error bounds on the computed values for the equations system'"'"'s dependent variables are listed in the last row of the tabular array.

15. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to a partial differential-algebraic equations system.

16. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to a partial differential-algebraic equations system comprising:

receiving initial values from the variables in the second group of the cells;

receiving boundary points values and corresponding boundary condition formulas from an additional group of the cells; and

utilizing the graph evaluator to evaluate said boundary conditions formulas in accordance with the underlining algorithm.

17. The method of claim 15, wherein displaying the solution comprises displaying values of the solution in a tabular array of the cells;

wherein values of the equations system'"'"'s first independent variable are listed in ascending order in a first column of the tabular array;

wherein values of the equations system'"'"'s second independent variable are listed in blocks of ascending order in a first row of the tabular array; and

wherein values of the equations system'"'"'s dependent variables are listed in multiple columns, such that values in each dependent variable column correspond to the values of the first independent variable in the first column and the value of the second independent variable in the first row; and

wherein corresponding label for the equations system'"'"'s second independent variable is displayed in the first row of the tabular array; and

wherein corresponding labels for each of the remaining equations system'"'"'s variables are displayed in a second row of the tabular array.

18. The method of claim 4, wherein evaluating the formula expression of the solver function computes and displays the solution to a system of algebraic equations and zero, or more inequalities.

19. The method of claim 4, wherein the solver function receives additional optional arguments for controlling the underlining algorithm and the displaying of the solution.

20. The method of claim 4, wherein the solver function receives from an additional group of the cells, formulas representing analytical Jacobian of said one or more root formulas with respect to the variables.

21. The method of claim 1, further comprising utilizing a first and second solver functions of said spreadsheet software application for computing an optimized solution to a parameterized equation system which satisfies one or more constraints, wherein the parameterized equation system is represented by one or more root formulas in a first group of the cells, variables for said root formulas in a second group of the cells, and design parameters for the parameterized equation system in a third group of the cells, said design parameters having initial values in the third group of the cells;

and

wherein the first solver function, using the graph evaluator in conjunction with a first underlining algorithm, and having one or more first input arguments, receives at least the identifiers for the first and second groups of the cells; and

wherein evaluating a first formula expression of the first solver function in a fourth group of the cells computes and displays, in the fourth group of the cells, an initial solution to the parameterized equation system in accordance with the initial values of said design parameters; and

wherein the second solver function, using the graph evaluator in conjunction with a second underlining algorithm, and having one or more first input arguments, receives at least the identifiers for the third group of the cells, and the identifiers for a fifth group of the cells containing one or more constraint formulas representing the constraints for the parameterized equation system, said one or more constraint formulas referencing the initial solution in the fourth group of the cells; and

wherein evaluating a second formula expression of the second solver function, in a sixth group of the cells, computes and displays, in the sixth group of the cells, optimal values of said design parameters, yielding the optimized solution.

22. A computer apparatus configured to perform all steps of the method of claim 1.