Geek Answers Handbook

Code Generation for Math Problems

I would like to write a program that describes a mathematical (optimization) problem, analyzes it and generates a compact, efficient C-code that solves it. I have a hacked solution to a much smaller, more specific problem in python, but it is ugly and just relies on templating C code, so I have a whole mess of lines that look like

for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

And then there is a mess of complex conditional logic, and at some point the above line is written to solve_problem.c after filling in the correct% s values.

In fact, it becomes much more complicated, because, as a rule, the problem is parameterized by matrices with a certain structure, etc., and the above approach, being efficient, starts to fall apart under its own weight.

So, I believe what I'm looking for is high-level tips on how to represent these problems in code, or rather, just examples of other projects where this has been resolved. Someone told me to use OCaml or F # and look at FFTW, but something simpler would be appreciated.

I am sorry that I am so slurred, but it’s hard for me to even express what I’m looking for myself, which, I think, is the root of the problem.

+6
source share
5 answers
 for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

You are requesting ways to present the code as described above. This can be represented by the value:

 For("k", Int 0, Leq(Var "k", a), Set("k", Add(Var "k", b)), SetElt(Var "a", Var "k", Mul(Div(GetElt(Var "v", Var "k"), c, GetElt(Var "a", Var "i")))))

This type is specified:

 type Expr = | Int of int | Var of string | Leq of Expr * Expr | Mul of Expr * Expr | Div of Expr * Expr | Set of string * Expr | SetElt of Expr * Expr * Expr | GetElt of Expr * Expr | For of string * Expr * Expr * Expr

I wrote a very simple high-level virtual machine called HLVM, which may be useful because it uses such representations in a simple way. The definitions are here , and a bunch of tests written using these definitions are here .

This representation is much more powerful than line switching, because the template matching compiler does exhaustive and redundant checks for you, making it easy to write functions over values ​​of this Expr type, including optimization runs and code generators.

+8
source

You are trying to implement a compiler, and that is how you should approach your problem. There is an input language that describes your optimization problem, and the output language is C.

You can eliminate your problem in the following tasks (not necessarily in this order):

  • Create a data structure that represents the abstract syntax for your input language.
  • Create a data structure that represents the abstract syntax of your output language, which in your case (a subset) of C.
  • Design the specific syntax of your input language.
  • Embed a lexer and parser that translates a particular syntax into abstract syntax.
  • Introducing a pretty printer that converts the abstract syntax of your output language into specific syntax.
  • Embed a compiler that outputs the optimization problem expressed in abstract syntax to a result again expressed in abstract syntax.

If you do not use languages ​​and compilers, you will be tempted to use shortcuts. For example, you can consider parsing using regular expressions. Or you might think that it’s a good idea to skip the abstract syntax and just generate the C source directly. I am categorically against this. Abstraction is your friend because it will make your problem manageable.

You must carefully choose the language in which you will implement all this. Of course, something like Ocaml is perfect for the job. But if you don't already know Ocaml, you should just stick to whatever language you like best. You should not try to implement parsers manually, there are many parser generators there. It is worth exploring. You can find my PL Zoo .

+3
source

I don’t know how much background you have in optimization, but I doubt that the path you have described is the path. In particular, I would be surprised if you could write effective C code to solve optimization problems, unless you limit yourself to certain classes of problems. Optimization usually distinguishes between different types of tasks (linear or non-linear, integer and continuous compared to mixed integer programming), each of which usually uses very different algorithms to solve the solution.

You might want to check out the Microsoft Solver Foundation for some ideas. Essentially, MSF is a common API that allows you to declare your problem in several forms (OML, a declarative language for defining optimization problems, as well as C # and F #), and then passes the problem to the appropriate solver, given the nature of the problem.

+2
source

I don’t know, it's easier. Invite you to take a look at existing work on mathematical modeling. I would not expect it to be simple; decisive codes are quite complex and more difficult to generate.

You need ways to specify the details of your problem and means to assemble parts of the response that are driven by this data.

I recommend:

Sinapse - a system for generating mathematical modeling codes; this article talks about how knowledge is organized and the generation of finite difference codes is supported,

and

The solution of equations of finite difference order , the thesis of MIT in the same vein.

(I worked on the Sinapse system during its initial development).

+1
source

It sounds like you want something like a symbolic calculation. Take a look at some implementations, such as:

In general, when trying to find optimization packages, many support some kind of symbolic representation.

+1
source

More articles:


All Articles