# Maze Master

Member

146

510 Good

• Rank
Member

• Website
1. ## Computing an extreme point of a convex polyhedron faster than linear time?

The problem of computing the extreme value of a polytope is called linear programming in the mathematics community. Your "hill climbing" method looks to be the same as the Dantzig's simplex algorithm. The main difference is the data structure - whereas you have a point cloud, the standard representation for linear programming is a system of linear inequalities.   There are theoretical bad situations where the simplex algorithm could perform very poorly (taking a number of steps proportional to the number of vertices), but people saw that these bad situations never happened in practice. Why the simplex algorithm does so well in practice despite poor theoretical guarantees was a point of confusion among researchers for a long time, until the algorithm was analyzed with smoothed analysis. It is now known that if you take a bad situation and randomly perturb it by a very small amount, it becomes a good problem.
2. ## Question about free variables, parameters, particular solution in vector notation

Here's some great video lectures that might be of help as you're learning linear algebra, http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/

4. ## Techniques to avoid skinny triangles with constrained delaunay triangulation

Jonathan Shewchuk (author of the code triangle) has an excellent paper about constrained Delaunay mesh refinement here: http://www.cs.berkeley.edu/~jrs/papers/2dj.pdf   A lot of his papers deal with this type of thing and are very readable, see here: http://www.cs.berkeley.edu/~jrs/jrspapers.html#delref   The basic idea is to find triangles whose circumcircle contains the vertex of another triangle, then "pop" the triangle by placing a new vertex in the center of the circumcircle and recalculate the mesh locally. After repeating this process enough (and dealing with constraints and boundaries in a way detailed in the paper), the process will eventually end with a (refined) mesh that has no thin triangles.
5. ## Matrix inversion

This is a rank-1 update to a very nice matrix, so you could use the Sherman-Morrison formula: http://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula   Here A =      [1    -1     0     0     0     0     0     0     0     0     0     0     0     0      0     1    -1     0     0     0     0     0     0     0     0     0     0     0      0     0     1    -1     0     0     0     0     0     0     0     0     0     0      0     0     0     1    -1     0     0     0     0     0     0     0     0     0      0     0     0     0     1    -1     0     0     0     0     0     0     0     0      0     0     0     0     0     1    -1     0     0     0     0     0     0     0      0     0     0     0     0     0     1    -1     0     0     0     0     0     0      0     0     0     0     0     0     0     1    -1     0     0     0     0     0      0     0     0     0     0     0     0     0     1    -1     0     0     0     0      0     0     0     0     0     0     0     0     0     1    -1     0     0     0      0     0     0     0     0     0     0     0     0     0     1    -1     0     0      0     0     0     0     0     0     0     0     0     0     0     1    -1     0      0     0     0     0     0     0     0     0     0     0     0     0     1    -1      0     0     0     0     0     0     0     0     0     0     0     0     0     1] u= [-11.7, 63.5,  -213.2,  493.1,  -831.8, 1055.7,  -1024.0,  762.9,  -434.5,  186.2,   -58.2,  12.6,  -1.7,  0.1]' v=[1,0,0,0,0,0,0,0,0,0,0,0,0,0]' Interestingly, some matlab calculations reveal this:   inv(A)=         [1     1     1     1     1     1     1     1     1     1     1     1     1     1      0     1     1     1     1     1     1     1     1     1     1     1     1     1      0     0     1     1     1     1     1     1     1     1     1     1     1     1      0     0     0     1     1     1     1     1     1     1     1     1     1     1      0     0     0     0     1     1     1     1     1     1     1     1     1     1      0     0     0     0     0     1     1     1     1     1     1     1     1     1      0     0     0     0     0     0     1     1     1     1     1     1     1     1      0     0     0     0     0     0     0     1     1     1     1     1     1     1      0     0     0     0     0     0     0     0     1     1     1     1     1     1      0     0     0     0     0     0     0     0     0     1     1     1     1     1      0     0     0     0     0     0     0     0     0     0     1     1     1     1      0     0     0     0     0     0     0     0     0     0     0     1     1     1      0     0     0     0     0     0     0     0     0     0     0     0     1     1      0     0     0     0     0     0     0     0     0     0     0     0     0     1]     Also,  1+v'*invA*u = 1.0000e-06 Now at this point you could use just perform the above sequence of calculations to solve the linear system So... putting this together invM = invA-(invA*u*v'*invA)/(1+v'*invA*u)    1.0e+08 *   Columns 1 through 11     0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    0.0100    -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069   -0.1069     0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    0.5286    -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033   -1.6033     3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    3.3276    -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909   -4.9909     5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    5.5661    -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740   -4.6740     2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    2.9553    -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897   -1.3897     0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    0.4724    -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099   -0.1099     0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    0.0157    -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   -0.0010   Columns 12 through 14     0.0100    0.0100    0.0100    -0.1069   -0.1069   -0.1069     0.5286    0.5286    0.5286    -1.6033   -1.6033   -1.6033     3.3276    3.3276    3.3276    -4.9909   -4.9909   -4.9909     5.5661    5.5661    5.5661    -4.6740   -4.6740   -4.6740     2.9553    2.9553    2.9553    -1.3897   -1.3897   -1.3897     0.4724    0.4724    0.4724    -0.1099   -0.1099   -0.1099     0.0157    0.0157    0.0157    -0.0010   -0.0010   -0.0010   And it seems to be decently accurate: norm(invM*M-eye(14)) ans =    9.5220e-05 This is pretty good, but if you want to go further, in practice you might instead apply the inverse to solve a particular system rather than computing the full inverse. In that case you can just do the matrix multiplications in the sherman-morrison formula to your right hand side vector one at a time.
6. ## Links to Pseudo-random Theory?

http://people.seas.h...cnotes/list.htm Harvard graduate course on the subject, taught by a expert, with free book/lecture notes! Kabam!
7. ## Advanced Mathematics for Computer Science

Haha, this thread got out of hand rather fast didn't it! I actually just got this book for the basics of category theory and it seems pretty readable so far.
8. ## Advanced Mathematics for Computer Science

Do you have any recommendations for category theory learning materials (books, videos, websites, online courses, etc..)? I've been trying to learn the basics for a while now without much success..
9. ## Advanced Mathematics for Computer Science

If you're interested in abstract Algebra, you might want to check out the harvard video lectures by Benedict Gross; they're really good: http://www.extension...bstract-algebra For (convex) optimization, there are two great video lecture series by Steven Boyd at stanford: http://academicearth...-optimization-i http://academicearth...optimization-ii For numerical analysis and more advanced numerical linear algebra, I really liked Gilbert Strang's (MIT) computational engineering videos, http://academicearth...d-engineering-i http://academicearth...or-engineers-ii For a lot of the topics mentioned (topology, differential geometry, nonlinear dynamics, etc), basically anything where there is a continuum instead of just finite structures, it will be difficult to make much progress without a solid grounding in real analysis. There's a great set of video lectures by Francis Su from Harvey Mudd where I did my undergrad, http://beta.learnstream.org/course/6/ (or http:/ and click through to the other videos)
10. ## Advanced Mathematics for Computer Science

I second discrete mathematics, and linear algebra as a background for computer science. However I'm an applied mathematics grad student who also programs, not a true "computer scientist", so take it with a grain of salt.. These subjects can be taught at a low or high level in a class, but the subjects themselves run quite deep. Linear algebra becomes functional analysis, operator algebras, etc - fields of current research. Discrete math branches into combinatorics, graph theory, etc. You don't have to look far in discrete mathematics to stumble on unsolved problems.
11. ## SAT Revisited

Even though you already figured it out, here is my favorite example for people who read this thread in the future. It's just two boxes close to each other but offset:
12. ## Linear Algebra and Calculus 3

For linear algebra, the Khan academy videos are pretty good: http://www.khanacademy.org/?video=linear-algebra--introduction-to-eigenvalues-and-eigenvectors#linear-algebra also, Gilbert Strangs MIT video lectures I recommend extremely highly: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/
13. ## PVS for constrained Delaunay triangulation

For closed compact path-connected sets, local convexity implies global convexity. This means, inspect the boundary of the set with a magnifying glass. If, nomatter where you look, the part of the set you see in the magnifying glass is convex, then the set is globally convex. If I understand correctly, the method you're using will create sets with no holes, bounded by straight lines, and with the corners having interior angles less than 180 degrees. This means it is locally convex everywhere on the boundary, which means it is globally convex.
14. ## Calculus of Variations

I think being really comfortable with linear algebra would be the best preparation. Intuitively one can think of a function as being a vector with an infinite number of components (eg, the value at every point). You can add and subtract functions (pointwise), multiply them by scalars, measure their "size", etc just like vectors. So, like a n-dimensional vector is a point in an n-dimensional vector space, a function is a point in an infinite dimensional function space. Functionals like "length of a curve" are just functions on the function space of all curves - imagine some sort of mountainous landscape where the x/y coordinates represent which curve you have, and the z coordinate represents the length of that curve. Finding the curve with the minimum length is like finding the lowest valley in your landscape. The space of curves can't be represented by just 2 coordinates (x/y) - you need an infinite number of coordinates - but other than that this picture is the right one to think of. For example, the tangent (hyper)plane to the lowest point in the valley must have zero slope in every direction. The way to find these slopes is with the Frechet (for one slope, Gauteaux) derivative, which is basically a big word for what you would already think of: lim ||h||->0 (f(x+h)-f(x))/(||h||).
15. ## General Transformation Matrix

I think the following video lecture gives some good intuition about this, especially the part where he talks about the "column picture": http://ocw.mit.edu/c...near-equations/