Commits

Hakan Ardo committed 393cd11

applied patch from cfbloz fixing typos

Comments (0)

Files changed (6)

 <html>
 <body>
-<H1>Linear programming</H1>
-Fancy hi-level interfaces often comes with a high runtime overhead
+<H1>Playing with Linear Programming on PyPy</H1>
+Fancy hi-level interfaces often come with a high runtime overhead
 making them slow. Here is an experiment with building such an
-interface using constructions that pypy should be good a
-optimizing. The idea is to allow the jit in pypy to removed the
+interface using constructions that PyPy should be good at
+optimizing. The idea is to allow the JIT in PyPy to remove the
 overhead introduced by using a fancy high-level python interface
-ontop of a low-level C interface. The application considered is
+on top of a low-level C interface. The application considered is
 <a href="http://en.wikipedia.org/wiki/Linear_programming">Linear
 programming</a>, which is a tool used to solve linear optimization
 problems. It can for example be used to find the nonnegative values
 <center><div class="eq"><img alt="" src="eqsource4.png" /></div></center>
 
 <p />
-There exists general propose solvers for these kind of problems that
+There exists general purpose solvers for these kind of problems that
 are very fast and can literally handle millions of variables. To use
 them however the problem has to be transformed into some specific
-standard matrix form, and the coefficients of all the matrixes
+standard matrix form, and the coefficients of all the matrices
 has to be passed to the solver using some API. This transformation is
 a tedious and error prone step that forces you to work with matrix
 indexes instead of readable variable names. Also it makes maintaining
 standard form of glpk (which involves introducing three new variables)
 and then gives the <a href="sample.c">c-code</a> needed to call the
 library. Relating that c-code to the problem above without the
-intermediate explanation of the the manual is not easy. A common
+intermediate explanation of the manual is not easy. A common
 solution here is to build a hi-level interface that allows a more
-natural way of defining the matrixes and/or allow the equations to be
+natural way of defining the matrices and/or allow the equations to be
 entered symbolically. Unfortunately, such interfaces often become
 slow. For the benchmark below for example, 
 <a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>
 requires 20 minutes to setup a problem that takes 9.43 seconds to solve
-(this is a bit extreme, am I doing something wrong?).
+(this seems a bit extreme, am I doing something wrong?).
 
 <p />
-The high-level interface constructed ontop of the
+The high-level interface I constructed on top of the
 <a href="ftp://ftp.gnu.org/pub/gnu/glpk/">glpk</a> library is 
 <a href="https://bitbucket.org/hakanardo/pplp">pplp</a> and it allows
 the equations to be entered symbolically. The above problem can be
 </pre>
 
 <p />
-To benchmark the API it was used to solve a 
+To benchmark the API I used it to solve a 
 <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem">minimum-cost
-  flow problem</a> with 154072 nodes and 390334 arcs. The c library
+  flow problem</a> with 154072 nodes and 390334 arcs. The C library
   needs 9.43 s to solve this and the pplp interface adds another 5.89
-  s under pypy and 28.17 s under cpython. A large amount of time is
+  s under PyPy and 28.17 s under CPython. A large amount of time is
   still spend setting up the problem, but it's a significant
-  improvement over the 20 minutes required on cpython by
+  improvement over the 20 minutes required on CPython by
   <a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>. It is
   probably not designed to be fast on this kind of benchmark. I have
-  not been able to get cvxopt to work under pypy. The benchmark used is
-  availible <a href="https://bitbucket.org/hakanardo/pplp/src/default/benchmark/">here</a>
+  not been able to get cvxopt to work under PyPy. The benchmark used is
+  available <a href="https://bitbucket.org/hakanardo/pplp/src/default/benchmark/">here</a>
   
 
 

blog/eqsource1.png

Old
Old image
New
New image

blog/eqsource2.png

Old
Old image
New
New image

blog/eqsource3.png

Old
Old image
New
New image

blog/eqsource4.png

Old
Old image
New
New image
 <html>
 <body>
-<H1>Linear programming</H1>
-Fancy hi-level interfaces often comes with a high runtime overhead
+<H1>Playing with Linear Programming on PyPy</H1>
+Fancy hi-level interfaces often come with a high runtime overhead
 making them slow. Here is an experiment with building such an
-interface using constructions that pypy should be good a
-optimizing. The idea is to allow the jit in pypy to removed the
+interface using constructions that PyPy should be good at
+optimizing. The idea is to allow the JIT in PyPy to remove the
 overhead introduced by using a fancy high-level python interface
-ontop of a low-level C interface. The application considered is
+on top of a low-level C interface. The application considered is
 <a href="http://en.wikipedia.org/wiki/Linear_programming">Linear
 programming</a>, which is a tool used to solve linear optimization
 problems. It can for example be used to find the nonnegative values
 x, y and z that gives the maximum value of
 
-<p/>
+<p />
 <center><div class="eq">z = 10x + 6y + 4z,</div></center>
 
-<p/>
+<p />
 without violating the constraints
 
-<p/>
+<p />
 <center><div class="eq">x + y + z \leq 100</div></center>
 <center><div class="eq">10x + 4y + 5z \leq 600</div></center>
 <center><div class="eq">2x + 2y + 6z \leq 300.</div></center>
 
-<p/>
-There exists general propose solvers for these kind of problems that
+<p />
+There exists general purpose solvers for these kind of problems that
 are very fast and can literally handle millions of variables. To use
 them however the problem has to be transformed into some specific
-standard matrix form, and the coefficients of all the matrixes
+standard matrix form, and the coefficients of all the matrices
 has to be passed to the solver using some API. This transformation is
 a tedious and error prone step that forces you to work with matrix
 indexes instead of readable variable names. Also it makes maintaining
 an implementation hard since any modification has to be transformed
 too.
 
-<p/>
+<p />
 The example above comes from the manual of
 the <a href="ftp://ftp.gnu.org/pub/gnu/glpk/">glpk</a> library. That
 manual continues by describing how to convert this problem into the
 standard form of glpk (which involves introducing three new variables)
 and then gives the <a href="sample.c">c-code</a> needed to call the
 library. Relating that c-code to the problem above without the
-intermediate explanation of the the manual is not easy. A common
+intermediate explanation of the manual is not easy. A common
 solution here is to build a hi-level interface that allows a more
-natural way of defining the matrixes and/or allow the equations to be
+natural way of defining the matrices and/or allow the equations to be
 entered symbolically. Unfortunately, such interfaces often become
 slow. For the benchmark below for example, 
 <a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>
 requires 20 minutes to setup a problem that takes 9.43 seconds to solve
-(this is a bit extreme, am I doing something wrong?).
+(this seems a bit extreme, am I doing something wrong?).
 
-<p/>
-The high-level interface constructed ontop of the
+<p />
+The high-level interface I constructed on top of the
 <a href="ftp://ftp.gnu.org/pub/gnu/glpk/">glpk</a> library is 
 <a href="https://bitbucket.org/hakanardo/pplp">pplp</a> and it allows
 the equations to be entered symbolically. The above problem can be
     print x.value, y.value, z.value
 </pre>
 
-<p/>
-To benchmark the API it was used to solve a 
+<p />
+To benchmark the API I used it to solve a 
 <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem">minimum-cost
-  flow problem</a> with 154072 nodes and 390334 arcs. The c library
+  flow problem</a> with 154072 nodes and 390334 arcs. The C library
   needs 9.43 s to solve this and the pplp interface adds another 5.89
-  s under pypy and 28.17 s under cpython. A large amount of time is
+  s under PyPy and 28.17 s under CPython. A large amount of time is
   still spend setting up the problem, but it's a significant
-  improvement over the 20 minutes required on cpython by
+  improvement over the 20 minutes required on CPython by
   <a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>. It is
   probably not designed to be fast on this kind of benchmark. I have
-  not been able to get cvxopt to work under pypy. The benchmark used is
-  availible <a href="https://bitbucket.org/hakanardo/pplp/src/default/benchmark/">here</a>
+  not been able to get cvxopt to work under PyPy. The benchmark used is
+  available <a href="https://bitbucket.org/hakanardo/pplp/src/default/benchmark/">here</a>