Maze Master

Members
  • Content count

    146
  • Joined

  • Last visited

Community Reputation

510 Good

About Maze Master

  • Rank
    Member

Personal Information

  1. 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. 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/
  3. I've worked a lot with matrix calculus and tensors (phd student, use it in my research all the time). In this post I'm going spend a lot of time explaining the basic ideas/techniques in the way I think about them, and then at the end apply it to your problem. Eventually we get a formula for the derivative object you want, K.     ---- Background ----   If you want to generally understand matrix calculus, it's much easier if you get comfortable with tensors. Tensors are not so bad. The most important thing is understanding how to unfold them into matrices or vectors, do something to them, and then fold them back up into tensors. If you become comfortable with that, then everything becomes straightforward. The first few sections of this paper are really good, with pictures: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153.2059&rep=rep1&type=pdf   If you have access to matlab and you want to get an intuitive feel for tensors, then I'd highly suggest making up tensors/higher dimensional arrays and playing around with the commands "reshape" and "permute" to get a feel for how it works.     ---- Meaning and application of the third order derivative tensor ----   Ok now back to the original question. Let's think about a N-by-N matrix, A, parameterized by k variables, A(x_1,...,x_k). If you take the derivative, you get a k-by-N-by-N box of numbers A_prime, where  - the first slice A_prime(1,all,all) is the derivative of A with respect to x_1,  - the second slice A_prime(2,all,all) is the derivative of A with respect to x_2,  - and so forth.   The first order of business is to understand how this third order tensor is applied to a vector to give the directional derivative in any given direction, v. The meaning of this directional derivative we want just what you expect - if you evaluate the matrix at the point X and at a nearby point X + epsilon*v, then how much does the matrix change. Ie,   [derivative of A in the direction v] = lim_s->0 (A(x1 + s*v1, x_2 + s*v2, ..., xk + s*vk) - A(x1, x_2, ..., xk))/s   To apply the third derivative tensor to a vector, you unfold A_prime into a k-by-N^2 matrix so as to expose the first mode to the left, and then left-multiply by the vector you are applying, and then fold the result back up into a tensor of one lower dimension (N-by-N matrix), like so:   [derivative of A in the direction v]  =  reshape(v^T * reshape(A_prime, k, N*N), N, N)^T     ---- Including right matrix multiplication ----   The next order of business is to understand what to do when there is another matrix B multiplying on the right,   [derivative of A in the direction v]*B   Obviously if we had 'v', we could apply the reshaping procedure to find the derivative, and then multiply by B. However, we want to think of v as being a free variable, and find the object that describes the whole process at once. In other words, what is the 3rd order tensor, K, such that, when you do the standard reshaping and multiplying process, you get the desired result.   [derivative of A in the direction v]*B  =  reshape(v^T * reshape(K, k, N*N), N, N)^T //what is K though?   To get this K, we unfold A_prime to expose the rightmost mode, then rightmultiply by B, then fold it back up:   K = reshape(reshape(A_prime, k*N, N)*B, k, N, N)     ---- Including left matrix multiplication ----   Now we know how to deal with matrices multiplying on the right, but what about if there is a matrix multiplying on the left instead? Ie:   B*[derivative of A in the direction v]   To deal with this, you have to permute the dimensions of the tensor to gain access to the left matrix mode, then unfold it, then left multiply by B. After that, you fold it back up and undo the permutation. The necessary permutation to move the middle mode to the left is [2,1,3], since that takes (k,N,N) -> (N,k,N). The inverse permutations is also [2,1,3] to do (N,k,N) -> (k,N,N). In detail, the overall tensor for the derivative and left multiplying process is,   K = permute(reshape(A*reshape(permute(A_prime, [2,1,3]), N, k*N), N, k, N), [2,1,3])     ---- Including matrix sandwich ----   Ok, finally what about the combination of both - when the derivative is sandwiched inbetween matrices like so:   B*[derivative of A in the direction v]*C   Here you just do both of the things we did before - unfold to expose the right mode, right multiply by C, fold back up, permute and unfold to expose the middle mode on the left, left multiply by B, fold back up, and unpermute.   K = permute(reshape(B*reshape(permute(reshape(reshape(A_prime, k*N, N)*C, k, N, N), [2,1,3]), N, k*N), N, k, N), [2,1,3])     ---- Application of the techniques to your problem ----   This covers all the cases necessary to deal with this sort of matrix equation. In our case, we seek to find a 3rd order k-by-N-by-1 tensor, K, such that   reshape(v^T * reshape(K, k, N*N), 1, N)^T = ... [derivative of A in direction v]*B*b + ... A*[derivative of B in direction v]*b + ... A*B*[derivative of b in direction v]   Using the above techniques, the tensor is K = K1 + K2 + K3, where     K1 = reshape(reshape(A_prime, k*N, N)*B*b, k, N, 1) K2 = permute(reshape(A*reshape(permute(reshape(reshape(B_prime, k*N, N)*b, k, N, 1), [2,1,3]), N, k*1), N, k, 1), [2,1,3]) K3 = permute(reshape(A*B*reshape(permute(b_prime, [2,1,3]), N, k*1), N, k, 1), [2,1,3])   Since b is a vector not a matrix, some of the stuff above is extraneous. Basically we can remove singleton dimensions like (k,N,1) -> (k,N), and replace permute [2,1] with a matrix transpose. These simplifications lead to the following form.   K1 = reshape(reshape(A_prime, k*N, N)*B*b, k, N) K2 = (A*reshape(reshape(B_prime, k*N, N)*b, k, N)^T))^T K3 = A*B*b_prime^T   and application via,   [derivative of f in direction v] = (v^T * K)^T   ---- Conclusion ----     Hope this helps. It's a lot to absorb, but it eventualy makes sense. It took me a long time to understand this stuff, but I think the learning process could be greatly expedited if you play around with reshaping and permuting multidimensional arrays. Other than the paper linked at the start I haven't found many good resources to learn from. 
  4. 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?

    [quote name='Expert Novice' timestamp='1335226203' post='4934285'] Can anyone link me to some pseudo-random papers or websites? [/quote] [url="http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm"]http://people.seas.h...cnotes/list.htm[/url] Harvard graduate course on the subject, taught by a expert, with free book/lecture notes! Kabam!
  7. Advanced Mathematics for Computer Science

    [quote name='daviangel' timestamp='1333676019' post='4928647'] Wow how'd we get on this tangent [img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img] [/quote] Haha, this thread got out of hand rather fast didn't it! I actually just got [url="http://www.amazon.com/dp/052171916X/?tag=stackoverfl08-20"]this book[/url] for the basics of category theory and it seems pretty readable so far.
  8. Advanced Mathematics for Computer Science

    [quote name='alvaro' timestamp='1333392073' post='4927587'] I had to learn category theory in college and putting that stuff in my brain felt like hammering a square peg into a round hole. I had a similar feeling when I tried to learn functional programming. So I am not too surprised that the two are somehow connected. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] [/quote] 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: [url="http://www.extension.harvard.edu/open-learning-initiative/abstract-algebra"]http://www.extension...bstract-algebra[/url] For (convex) optimization, there are two great video lecture series by Steven Boyd at stanford: [url="http://academicearth.org/courses/convex-optimization-i"]http://academicearth...-optimization-i[/url] [url="http://academicearth.org/courses/convex-optimization-ii"]http://academicearth...optimization-ii[/url] For numerical analysis and more advanced numerical linear algebra, I really liked Gilbert Strang's (MIT) computational engineering videos, [url="http://academicearth.org/courses/computational-science-and-engineering-i"]http://academicearth...d-engineering-i[/url] [url="http://academicearth.org/courses/mathematical-methods-for-engineers-ii"]http://academicearth...or-engineers-ii[/url] 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, [url="http://beta.learnstream.org/course/6/"]http://beta.learnstream.org/course/6/[/url] (or http:/ /www.youtube.com/watch?v=sqEyWLGvvdw 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: [img]http://i.imgur.com/TmUUm.png[/img]
  12. Linear Algebra and Calculus 3

    For linear algebra, the Khan academy videos are pretty good: [url="http://www.khanacademy.org/?video=linear-algebra--introduction-to-eigenvalues-and-eigenvectors#linear-algebra"]http://www.khanacademy.org/?video=linear-algebra--introduction-to-eigenvalues-and-eigenvectors#linear-algebra[/url] also, Gilbert Strangs MIT video lectures I recommend extremely highly: [url="http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/"]http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/[/url]
  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": [url="http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-1-the-geometry-of-linear-equations/"]http://ocw.mit.edu/c...near-equations/[/url]