Distinguished Seminar in Computational Science and Engineering: Justin Solomon, 12/11/2025

We're going to change that someday. Bridges those worlds. And so that's--

Well, thank you so much. That's a very kind introduction, Yusuf. It's such a pleasure to talk to you guys. And this is useful because I got irresponsible about interfacing with the CSE community the last couple of years because things are just busy and messy. So it was nice to have the excuse to come see everybody's faces here and hopefully attract some of y'all to hang out in our lab. So today, I thought I would tell you about some of the research that half of my research group is doing. And I'll tell you a little bit why that thing's bifurcated a little bit. As a bit of a warning, as many lazy professors do during final exam week, there's some reused materials here from a talk for a graphics conference, which isn't perfectly calibrated to the audience here. At any point, please stop me if there's questions or if you're bored and I'm covering elementary stuff. That's perfectly fine. Just give me a good kick, and we'll move on to the next topic. But I thought I would tell you about some of the research projects that our group has done over the last couple of years, specifically the intersection of optimization and this application area, which I would argue really is part of the CSE core set of machinery, although at MIT is considered somehow part of the computer science AI universe, which is this area of geometry processing.

Before we get there, because this is an audience that I really should be interfacing more with on this campus than I have recently and it's been a little while, so just in case we haven't had the opportunity to meet, my name is Justin. I lead a group in CSAIL across the street. In CSAIL, we're supposed to give a corny name to our research lab. So we converged on Geometric Data Processing, which I'm going to hopefully convince you guys is a totally ambiguous term by construction. But really, we're one of these funny research groups that's sitting at the intersection of a bunch of stuff. And we're always looking for new problems and collaborations and all kinds of different domains, everything from numerical PDE to applications and also to some high dimensional machine learning statistics problems too, which is a funny byproduct of my own PhD. And maybe I'll mention that in a second. Incidentally, I should mention we actually have an opening in our lab specifically for a weird project, an acoustic simulation. So if wave equations are your bag, let me know. This is not a topic I actually know anything about, but we have a fun new partnership. And I'd love some help with that.

So from a broad perspective, what our research group does, we work in this funny area of geometric data processing, which is a funny Bert and Ernie situation of two very different fields, at least in the computational domain, that we've glued together. This is a byproduct of my own PhD. So roughly, when I was at the stage of many of the students in this room, my PhD was in an area of math and computation called optimal transport, which at the time was this hot new thing in probability theory that was being slowly moved in the computational domain. And we all thought it was going to be exactly what we needed for keyframed animation in computer graphics. Now, what if-- go gosh, 15 years in retrospect, I can tell you that was a terrible idea. Optimal transport is not a good fit for computer animation because the whole point of optimal transport problems is to be as boring as possible, which is not what animators want. But in the process, we ended up in this funny domain where my background was in computer animation and actually had worked at Pixar before going into grad school, but then the work that we were doing ended up being applicable to very high dimensional problems and probability. And so our research bifurcated that way. So we have half of our team working on, I think, what you would consider to be conventional geometry problems in computation. So usually those are 2 and 3 dimensional, working with friends in computer animation and physical simulation and computer vision. For example, there's a-- grabbed a random LiDAR scan from a data set we had around. And then the other half of my research group works on high dimensional probability problems, inference, optimization, this kind of thing. And the running thesis of our research, which sometimes works and sometimes doesn't, is that the tool sets from a geometry perspective are not all that different between those two. In fact, we've had many PhD students that have worked on cool low dimensional problems in geometry processing, 3D graphics, and then realized the same Laplacian operators and transport problems and whatever are directly applicable to some problem in machine learning. And if we're really lucky, they get a two for one discount in research papers in terms of application domains and so on.

So today, pardon me, our focus will be in this former category. And in particular, I'm going to tell you about some research projects in our group in this field of geometry processing. Now for those of you who are uninitiated, there's a bunch of research areas that sound the same by name but actually are quite different from academia perspective. In particular, there's geometry processing and computational geometry, which sound identical, and to any rational human they would be. But it turns out just from perspective of evolution of research fields, those are two very different things. So in geometry processing, we're very concerned with this intersection between the smooth and the continuous and the discrete world. And it's a lot of using machinery from PDE and optimization, variational calculus to understand discrete 3D shapes for problems in modeling animation and so on. If you're curious, by contrast, I think computational geometry is typically purely discrete algorithmic problems like Voronoi diagrams, Delaunay triangulation, and so on. Now the line between these two areas is obviously very blurry. And I'll try to mention that. But just in case you're curious, that's the mild distinction here. Of course, it's also my pleasure to chat with everybody in this room about our research in this other domain of high dimensional geometry and probability and so on. We won't see too much of that in today's talk, but that's what the rest of our research group does. For instance, in the last year, somehow all of my grad students have converged on studying all kinds of weird properties of diffusion models from a theoretical PDE, SDE perspective, which is certainly a new one for me.

OK. So I thought we'd start very broad and then narrow in a bit in terms of technical content here. And when I was preparing this talk, which was this fun excuse, it was at this Eurographics conference, it was an excuse for me to take a lot of the work from our group and try. I feel like there's this phenomenon where we all grabbing at random research problems and then a posteriori glue them together into a coherent narrative and pretend like that was the story the whole time. And certainly, that's the case here. But I do think that our research is reflective of this quite broader trend in the computer science domain that I think in the CSE audience is a very familiar one. Now, my undergrad degree, I was dual in computer science and math. And I think the interesting thing when I look at MIT's curriculum, for example, is that what those two areas in their intersection looks like has completely evolved since the time that I entered my degree many, many, many years ago. And in particular, when I was studying computer science and taking most of the core classes in my discipline, it was programming discrete structures. And then when you took an algorithms class, it was all about problem solving in a particular reasoned fashion, where you talk about sorting numbers and binary trees and structures and for every problem, coming up with this very carefully matched set of algorithms that is tuned to your programming system and so on. But I think when you talk to a modern computer science student, their perspective is actually very different. This is a thing that I think we all know intuitively, but I thought I would call out that. I think now the reasoning we see even in the computer science domain is very much optimization oriented. And the computer scientists, largely due to the rise of AI systems, think a lot more in terms of objective functions and a lot less in terms of algorithms than we might have used to. And that revolution, in some sense, in computational thinking, really has affected not only the broad perspective you see in computer science, but also specifically this geometry processing domain, where it used to be that things really did look very discrete. We talked about meshes and Voronoi diagrams and so on. And now we're a little bit less concerned with that and more concerned with taking our geometry problems and imposing them in this very generic language. We're coming up with objective function, variables, constraints, and so on, which is obviously a very broad story. But of course, there's this interesting intuition that, I think, we all have, although sometimes we don't call it out, which is that as we convert to this language, we have enough of an understanding of the algorithms behind the scene to know which formulation is likely to be successful when we put it into maybe even just a totally generic toolbox for solving these problems. This is very different, again, from classical computer science, where you do this and then most of your time is spent actually coming up with a bespoke algorithm for solving this particular problem. So in geometry, we've had exactly the same kind of trends. It is not hard to take geometry problems and pose them in this language. So for example, the ones that we'll talk about today include closest point projections. So maybe I've given a point in R3. I want the closest point on that thing to a bicubic patch on this teapot, hopefully. By the way, this is, I guess, not a computer graphics audience. Is this teapot familiar? Really? Fascinating. This is one of the very first 3D models. This is the Utah teapot. There is a physical Utah teapot you can go find, I believe in Utah, and it is constructed out of bicubic patches. So these are the original 3D geometry that was used a lot in computer aided design. Incidentally, computing closest point on a bicubic patch is already a polynomial problem of high degree, so doing it in a nice fashion is already quite challenging. One that we're going to focus on a lot today is called texture mapping, where I take a 3D surface and I squash it into the plane. So an interesting observation in the geometry community is that we can often store geometry at a much lower resolution than texture. So for example, in your typical video game, your 3D models are comprised of these triangulated surfaces, but the triangles are often much bigger than a pixel on your screen. And then what happens is you map these things into the plane and you store a very high resolution, two dimensional texture that gets wrapped around a piece of gift wrap around the surface. Actually, computing that parametrization is a really challenging problem. It's been around forever in geometry, where you're trying to minimize the warp of the surface as it gets smashed into the plane so that equal pixels on the plane correspond roughly to equal amounts of surface area, for example, which turns out to be an impossibility, thanks to curvature. And so this is a thing that we have to navigate. Computer animation is another clear one where optimization makes a lot of sense. You have to pass through certain keyframes, maybe have certain desirable motion or a favorite pet problem of geometry processing is this thing we call frame field design, where you're given a 3D surface and your goal is to place little plus signs. This is a slight generalization of a vector field on a surface. And then what you do is if you want to extract a quadrangulation of this 3D surface, you maybe use the streamlines of this field as some way to guide that process. I should be clear that sentence is very reductive. The problem of placing those streamlines in a nice integer grid turns out to be the really hard part of this problem, which is something I can tell you all about but probably not today.

OK. So here's the interesting thing that we see in geometry processing literature in the last couple of years, which is cool, and again, very much reflective in this funny way of trends in machine learning which have affected us all. Even though this domain, at least, the problems I've presented you here are maybe not obviously machine learning problems. We spend a lot of time writing these very elegant formulations, how do you measure whether a frame field is desirable and so on, or even what is the topological space of frames for this particular problem? Not so hard in 2D and 3D. The space of pairs of triplets of axes up to rotation is a really weird quotient manifold, but I'll try not to get too distracted. But anyway, we spend a lot of time formulating these problems. And then what do we do? Well, we open up our favorite optimization toolbox in SciPy whatever. And we call basically one of two algorithms up to window dressing. If you have one derivative, then gradient descent seems like a reasonable match. If you have two derivatives, then maybe Newton's method. And of course, there's a very reductive story that I'm telling you. And there's many things in between this, BFGS, Nesterov, Adam. What's the new one that everybody likes this month? Muon. Whatever. But the thing to know is that all of these algorithms, including all the ones in SciPy, are completely agnostic. They don't know that you're solving a geometry problem. They're just out there trying to minimize functions f. And so I think a completely sensible and reasonable question, and one that many of us study in our own domain areas, is if we know a little more structure of our problem, can we use that to formulate algorithms that outperform the totally generic alternatives? I should be careful here. Sometimes the answer is no. For example, these toolboxes, especially for convex optimization, are shockingly good. And sometimes we'll spend all these times designing these projects and then run MOSEK, and it just outperforms. And it's sad and not predicted by theory. But the good news is that indeed, hopefully, what I can convince you today, is that geometry processing applications really can benefit from custom built methods. So essentially, if we open that black box, we think about what's going on in these procedures. We can do a little better than just following the things that we learn in our numerical methods 101 course.

OK. I think this story is pretty uncontroversial. So in particular, here's what we'll do. I'll tell you a little bit about what I think makes my field special, other than just my interest in it. And then I'll tell you about some of the generic strategies that you see in this domain, many of which are very familiar to this audience. But I thought I'd give you a bit of a flavor of how we think about, for example, preconditioning duals and convex relaxations and so on, specifically in this domain, which, interestingly enough, we're pretty unfamiliar tools, specifically in the geometry processing world, which really was lifted from computer graphics and computer science, rather than the numerical analysis world where many of these things will feel pretty trivial and small. And hopefully, I can convince actually many of the people in this room that if you're looking for a bunch of easy research problems, my guess is a lot of people that have experience in the numerical domain probably have a lot of things to share in this particular field because it's just a very different perspective and one that we're just beginning to map onto this field. I feel like with all these fancy, distinguished numerical methods professors in the room, I have to be very careful to don't talk everything I do. This is all boring. They probably already know it. It's predictable. Whatever.

OK. So let me tell you a little bit about why I think geometry processing is such a special and interesting area. And in particular, let's put it in the framework of one pet problem of this domain that's been around forever, and that's this problem of surface parameterization, which is as follows. I'm given some 3D surface like this cow from perspective of modern computer graphics is a very low resolution. Typically, these things are comprised of maybe millions of triangles that some artist has carefully designed or maybe you obtain with a 3D scanner or whatever. And your job is to take this cow and make it into a carpet. And this happens in basically two stages. So the first thing that you do is you puncture the cow somewhere so that he has disk topology. Or maybe you take a pair of scissors to the cow or whatever so that you can actually topologically roll this thing into a flat domain. Incidentally, quietly, a problem that we all should be solving and aren't is where to place that cut, which turns out to be really challenging and some combination of discrete and continuous mathematics. So for example, recently some people have applied some of the physical style mathematics of fracture to this problem to try to figure out where that might make sense. That is a largely open domain of problems in this area. But then the second problem is, once you've placed that cut, now you have to actually unroll this thing. And obviously, the geometry of this flat cow and the geometry of the 3D cow have some things in common and some things not. Namely, the guy on the right is flat. And in fact, whether you want to use fancy language from differential geometry or just high school math, you can very easily convince yourself that you can't really take all of the triangles on this cow and lay them out on the plane without basically distorting some of the edge lengths, with one exception, which is ungluing every single triangle and just putting them out on a row, which isn't a very exciting parametrization. And so typically when we formulate this problem, it maps very cleanly onto optimization language, at least at a high level, where now we have a variable for every vertex of the 3D cow where it should end up in the plane. And we probably have some loss function or objective, which is maybe a sum over all of the triangles of some notion of distortion, for example, the change in edge length, or these days, what's popular, which makes a lot of sense, is to take some constitutive model from elasticity and use that, basically pose this as a static physics problem, which makes sense and also doesn't make sense because there's some constraints to this that are pretty specific to the application. The variables here are pretty clear, and there's often many constraints. So for example, it turns out it's much easier to solve these problems if you know where the boundary goes. This is if you've taken a numerical PDE class and you know the boundary conditions are really important, somehow, in some sense, the optimality, like the KKT condition of this problem, is some discretization of a PDE. So it's not entirely surprising the boundary condition really matters. But moreover, there's actually a constraint that I think is a little bit harder to think about in PDE language, which is injectivity. So think about the application. If I have any two triangles from this 3D cow that get mapped to the same part of the plane. Now I put a texture on the plane. So for example, this little alphabet thing, which is what you use to debug. If you think about what's going to happen on the 3D model necessarily, there's going to be two different regions on the 3D model that have the same texture. So from the perspective of a computer graphics artist that could care less about elasticity and numerical methods and PDE and everything else, the second that this map is not injective, the whole thing is useless. Now from the language of constraint optimization, what does that mean? Well, in the most conservative sense, for every pair of triangles, those two triangles can't overlap, which is a really nasty constraint on this problem. And it's wildly non-convex for one thing. For another, it's arguably discrete in certain ways. There's all weird topological restrictions that happen. You don't expect gradient descent to work terribly well. And we'll come back to that in a bit. So hopefully, I've convinced you this is a very interesting large scale optimization problem. It looks very different from a neural network. And so from perspective of geometry, I think, there's so many different ways to think about these kinds of problems. For example, as a geometry guy, what I really like to think about is the fact that there's three different shapes that we have to navigate the relationship between, in this problem. There's the 3D surface, the 2D surface, and then the configuration space of the 3D guy. You can understand a lot of the parameterization techniques as choosing which of these geometries to favor when they're solving these optimization problems and then using that to come up with different gradient flow procedures. But beyond that, a lot of the generic algorithms that we might use in this domain turn out to fail for pretty obvious reasons. Now, to this audience, I'm guessing this story is pretty familiar. In computer graphics audience, it turns out this is a very reductive example that a lot of people don't think about, which is surprising to me when I presented it. So here's a very simple one. Let's say that I have a big rectangle that I've meshed in a really boring fashion. And my objective function is some notion of distortion per triangle. So I look at every single one of these triangles and my objective is 0 if this rectangle is a rectangle, and it gets large as the triangles get stretched out. Very reasonable objective. It's more or less what people do. So for example, if you're taking a graphics class, we're all obsessed with this particular energy called as rigid as possible, which is just a weird, almost linearized version of elasticity. And so obviously, parameterizing a two-dimensional rectangle is a problem that I think we could all solve. However, let's say that for whatever reason, I gave my optimization algorithm an initial guess, which was a little bit evil, and I just took that bar and I rotated it about its midpoint. So I put this L shape in. And my goal is to minimize distortion relative to the shape on the top. And now I take this energy on the top, and I do gradient descent. Now, it's pretty clear. For one, gradient descent will get you there if you wait long enough. But a thing that is maybe obvious, maybe not, depending on your experience, is that gradient descent is probably the worst possible algorithm for this problem. And let's think about why. So if I handed-- I take a metal bar, I bend it in half, and I hand it to Yusuf and I say, unbend it. What's he going to do? He'll grab the two sides of the 90 degree angle. He'll bend it back. And the question is, does that the motion that actually happens in the gradient descent procedure? Does it know that it needs to unbend this shape? And the answer is absolutely not. In fact, it doesn't know, for example, that this energy is rotation invariant. And so what is the gradient? Well, there's zero distortion here. The zero distortion here. So the gradient is 0 on the two sides of the bar, and all of the information about how to unbend it is sitting right at this point. This is a very familiar story. We know this in PDE and all kinds of different universes, but what does that mean? It means your gradient direction, which we can plot as a vector field, basically sits right at this edge. I take one step of gradient descent, and I get this thing, which I think we can all agree is not obviously progress, although it does turn out to slightly decrease the objective function. And so in reality, if you implement gradient descent on this kind of thing, which again, I don't think most people in this room would do, but it's maybe your first try. your optimization procedures tend to get stuck. In fact, here you're seeing this wiggly procedure where information propagates outward along the bar because in every step, you talk to your neighbors, and then now your neighbors are messed up and so on, and it propagates back inward. And a few hours later, eventually, you'll converge to the solution. So all this is to say that at least the default algorithms we think about in this domain are not super good. On the other hand, I could use Newton's method. Absolutely. It turns out Newton's method often fails for these problems because these problems are very, very non-convex. So basically a lot of models from elasticity struggle because elastic problems tend to have many different solutions. So think about taking a rubber thing and squishing it inward. It can buckle up or it can buckle down. Newton's method doesn't really know which one you want. And oftentimes OK locally, you can have this kind of procedure. And then you have almost discrete decisions that have to happen during optimization routine. Beyond that, so that's a headache of the objective function in, but the constraints are really hard too. So here's a really fun figure from my student year a couple years ago. This is not a thing anybody should do as a rational human, but it was a stress test for his algorithm, which is as follows. He took this 3D model, which was composed, I think, of roughly a million triangles. He punctured a hole right in the bottom of it, and then he mapped that thing into the letter G. I don't know why the letter G. Fun fact, this is actually injective, actually beyond numerical precision. He checked it with exact precision arithmetic. And if you think about it for, whatever reason, now obviously this is an extreme example, but in this parameterization problem, these are the kinds of things we have to deal with, is that injectivity is a really critical constraint and not a very well understood one mathematically. In fact, in order to justify the algorithm that he proposed two years ago, he had to dig through optimal control theory and managed to find an analogous problem in that community. Interestingly, actually, it has to do with boundary condition, which is surprising to me. I would have guessed that anyway. So in order to have a useful texture map, no two triangles can share the same part of the plane. Here's an interesting thing. Oftentimes, we think in optimization of at least, it's easy to find a feasible point to start with. This is not one of those problems. So for example, if I gave you this shape, and I told you to smash it into the letter G, and I just gave you all the vertex positions and said, I don't even care about the distortion, lay it out any way you want, it would not be obvious to me how to solve that. So even just getting an initial guess for a gradient descent procedure here is not so clear. And then finally, of course, these problems have many local optima. So for example, this is the failure mode figure from my student master's work. So I should be clear. He has an algorithm that often works. But this is the figure showing you what it doesn't. He worked on a problem involving correspondence. So you're given two volumes embedded in R3. And you want an injective map from one to the other. So his interest was in medical imaging from MRI. But we can also test on these crazy computer graphics examples just for fun. And there's just no shortage of places where, for example, he's mapping what a dolphin into a shark here. And you see some folding over, which is what you would expect. In fact, this even looks like you made this guy out of elastic material and tried to squish it into the other domain. Or in this case, there's almost a discrete variable that's hiding in his injective mapping problem, where because of the threads of the screw here, the optimization procedure has to decide how to do this very unnatural thing, to be clear. But these algorithms do these kinds of things locally of figuring out what it means to map one of these objects onto the other. So hopefully, I've convinced you guys. This is a hard domain. There's a lot of really tough problems. They tend to be extremely large scale, and they have constraints where artists are really picky. If we violate them ever so slightly, they just throw it out. And so on the other hand, for example, we have a lot of wiggle room that other domains don't have. I'm not solving Navier-Stokes equations. There's no physical model here. If my energy is too hard to optimize, I have the luxury of saying, then I choose another energy, which is not a thing that you get in a lot of corners of physics, for example. And so there's this interesting interaction between modeling and algorithms that we get to have that other domains don't. By the way, I should be absolutely clear. This is the point where typically when I speak to numerical analysis audiences, they check out because I feel like I'm often dismissed as oh, these graphics guys, they just do whatever they want. These are really hard problems and reflective of a lot of challenges you see in other domains. So in any event in the negative 30 minutes I have remaining, I thought I would tell you a little bit about some of the interesting strategies that our group has explored over the last couple of years. This is almost a high level advertisement for these papers rather than a deep dive into the math. But anytime you're bored of these things, let me know, and we'll just go to the blackboard and go through any of these in detail. And I took our last 10 years of work and then tried to cluster them a bit in terms of the kinds of strategies we use to make these problems more tractable. And a lot of these end up being basically the kind of strategies you see in an intro course in CSE. So I thought it was fun to call them out that way. Now, for example, I think the first thing we can mention is a classical strategy called preconditioning. And this has to do with that example with this gradient descent bar unfolding thing that we talked about before. Now, essentially, here's, I think, the observation that we all know and love from our own research domains is served up almost everywhere, which is the reason that we like gradient descent is because it's easy, but it's not particularly efficient. And particularly, there's this weird, counterintuitive fact that walking downhill is not a particularly efficient way to get to the minimum of a function. So for example, here, I think is the example that-- in fact, I think I just borrowed code from my own numerical analysis course that if you have a quadratic function, you do gradient descent. We know the gradients are orthogonal to the level sets, which obviously does not point you toward the minimizer. Here this is something that I'm sure almost everybody in this room has encountered in some version or another. And so I think we can understand a lot of algorithms in this domain is basically trying to reshape this landscape to be as circular as possible, in which case gradient descent actually is a reasonable algorithm, including Newton's method, which is in some sense trying to do that by taking a second order approximation. One way that we can reason about this, a lot of times when you read about gradient descent, people use the phrase descent direction. By the way, I did a fun thing. This semester. I'm teaching numerical methods, and I put a survey out to-- and this is for PhD students in EECS. Luca and I have some work to do because I asked the students, OK, so why does gradient descent work? And they all give you the same answer, which is well, gradient points downhill. And you say, well, what does that mean? The gradient is just this vector of partial derivatives. What does that have to do with the hill? And actually not a single student in the 70-student classroom had a very good answer to that, which was concerning. But from my perspective, this is really just a byproduct of Taylor series that, of course, is very easy to see that if I take first order Taylor approximation of our function f, then notice that if delta is our motion where we're going to move next, so long as this dot product is I guess positive, then at least our objective function will decrease as the weakest possible statement. But in a sense, this actually gives us a big space to do some modeling, which is to say that really anything whose dot product with grad f is in the same half space, which gives us some possible direction for decreasing our function locally. And in fact, there's a useful little theorem out there which many of us know intuitively, but it's worth calling out that essentially, if you take grad f and you multiply it by any positive definite matrix, then you still have a descent direction. The proof is a one liner. I put it there for fun. And so I think you can understand a lot of preconditioning strategies and in a very simplistic

fashion, as just choosing a nice positive definite matrix A to put in front of the gradient of your problem. And now, obviously, there's all kinds of beautiful theory around certain choices. But from my perspective actually, you can think intuitively here and use that to do some modeling and get a lot of benefit for these problems with very little change to these algorithms.

For example, the classical answer how to get a better gradient direction is something called Sobolev preconditioning, where essentially you change your inner product space to account for the gradient of an unknown function. So, for example, rather than taking dot products between gradient directions as just the sum over all the elements, if you instead took the dot products between the gradients of your functions like vector field, then that will induce basically sticking a matrix in front of your descent direction, which is the inverse of Laplacian up to some diagonal change.

And in effect, what that does is it takes our descent direction, and it makes this new guy over here. Now, I think the good news. I mean, if you crack open a numerical PDE textbook, you read about Sobolev preconditioning, it's all really scary. But I think the intuition here is actually quite simple, which is that information here needs to get there before you make a whole lot of progress on this problem. And in some sense, that's what these preconditioners are doing.

In fact, for fun, I had a grad student take this very carefully designed L inverse and replace it with a matrix whose elements are just completely random. And it turns out that the gain that you get for gradient descent is nearly the same as Sobolev preconditioning for this problem. That basically the main issue is just communication bandwidth rather than anything else, at least for this particular class of things. By the way, there's some interesting math to be done there that maybe it's actually not such a bad strategy. Yes, Laurent.

It's a good question. I think the difference between this area and deep learning is that here our variables are linked together in a very sparse fashion. This is true for a lot of PDE problems. Whereas in deep learning it's almost exactly the opposite. Everything is tangled together. You change one neuron and your entire performance. And so I don't actually know. I do think there's some super interesting efforts in deep learning.

Actually, our group has a project in this domain at the intersection of that and these physically informed neural networks, which asks a question that geometry processing people are obsessed with, which is, it would be really nice if I took 10 different remeshing of this model, and I looked at the sequence of 3D models you get throughout the gradient descent process at least as a function of iteration, and that they the same for these different resolution things.

You could ask the same question about neural network training, which is, if I add more neurons to my network, I expect each training iteration to be slower. But maybe can I come up with a procedure where a preconditioner for the training procedure so that the thing that gets slower is the time it takes to do one iteration of gradient descent but the number of iterations stays invariant, similar to invariant to resolution of a mesh. And it turns out those same strategies actually apply, which is cool.

I'll avoid getting distracted and writing that down, but I love to sketch it out because actually we have some fun ideas to think about in that domain. One interesting thing to note here, Sobolev preconditioning is a very generic answer from PDE theory as how to precondition these problems even to make sense, by the way. So if you look at the sequence of gradients you get as you refine the mesh, if you do the computational one, these directions get worse and worse and worse.

But this still doesn't look like a direction to unbend the bar. Notice what this thing wants to do. It takes the two sides of the bar, and it just moves them out. And so a reasonable question we ask is, is this generic answer from PDE theory really the right one for these problems in elasticity? And the answer is no. That in fact, our gradients for these problems are structured in an interesting way.

There's three or two coordinates per vertex here that matter, and that they're linked together in a particular fashion, moving x and y are not independent operations. And so in fact, my student Sebastian, many years ago proposed replacing Sobolev space with something called Killing space. Killing is a mathematician. Nothing violent. If you Google for Killing fields, you should be sure to search for Killing vector fields.

And essentially, this is a first order model for elasticity that can be used in an identical fashion to Sobolev preconditioning but is specific for problems involving rubbery stuff. It has very similar properties in theory in terms of what PDEs are well defined in this space. What we found is simply by replacing this matrix with this one that knows something about the problem we care about, this is not just a fun mathematical thing; it actually leads to the State of the art algorithm for these kinds of mapping problems.

So here is the typical plot you see with a horizontal axis, it's iteration or time. The vertical one is distortion. And obviously, the guy at the bottom is ours, or I wouldn't be showing it to you. Incidentally, if I catch any of the students in this room only giving the plot on the left hand side, then I'm not going to let you pass your dissertation defense because, obviously, for example, one way to make my algorithm twice as fast from the perspective of the left thing is to just say, oh, every iteration of my algorithm is two iterations of your algorithm, and suddenly I'm 2 times as fast.

So really, wall clock time is the relevant thing for these kinds of things. I think that's a thing worth pointing out, because I feel like in the machine learning community, that's gotten lost. But I digress. Yes.

Yes, absolutely. So specifically this Killing operator, what it does is cool. Actually discreetly, it's very easy to understand. You take a look at this field on the three vertices of a triangle and you measure. So that thing, if you think of it as a linear function along the triangle, which you can do, it turns out, sorry, number of degrees of freedom. And you look at the Jacobian of that function, you measure how far it is from being asymmetric. And that turns out to be the right notion of norm here.

And the way to think about that is that think about a rotational vector field. So minus y comma x. So if you think about the Jacobian matrix, it's exactly an asymmetric object. And so this is a Riemannian metric that only cares about the deviation from being a rigid motion. Yeah, it's a good intuition.

OK. So in any event, this was a nice example of an entire PhD thesis of material that was just based on a really intuitive observation, which is gradients in this field are bad. The default way to fix them didn't work terribly well. So let's think about this problem a little bit more deeply and maybe dig into some other weird function spaces that made sense.

Sometimes, we don't get so lucky, and there's other strategies out there. So for example, in computer graphics, the most popular algorithm and a different class of techniques is this thing called rigid as possible, whose job in life is to take some rest, pose of a shape. You deform a few vertices and you want to know where the rest of the shape goes. If you play with 3D modeling software, almost certainly some version of this technique is hiding in there somewhere.

And essentially, the way that they're able to solve this optimization problem is they take the variables and they divide them into two sets. One of them is the closest projection of the motion of the surface near a vertex onto a rotation. And then the other one is just the vertices. And it turns out if you hold one fixed and you optimize the other, you either get a linear problem or basically an SVD. And so that's why this algorithm is so fast.

And I think this falls into this category of basically alternating techniques where you take your variables, you split them into two sets. And then the idea is so long as one of these two things is tractable with the other fixed, then you have some nice algorithms for that. Incidentally, in the computer graphics literature, you read all these papers that say they have an as rigid as possible algorithm for solving problem x. And really what they mean is alternation. It's interesting that way.

So that's this particular case. We've had a lot of mileage in our research group basically taking the observation here, which is that a lot of problems in elasticity can be mapped onto these alternating techniques and then lifting these into more advanced and challenging problems for physics.

So most recently actually my student Leticia was studying problems involving simulation of elastic models, where now you have a very nonlinear energy. So these are all ones that blow up when things become singular. So if I take a triangle and I smash it into a point, then clearly real physics would be very unhappy with that. Whereas the standard models in computer graphics actually are perfectly fine with inversion.

And what she was able to show is that basically an extension of these kinds of alternating strategies applies to this in a way where you can guarantee that your simulation remains injective, so no elements ever flip over. And moreover, actually has provable convergence, which even as rigid as possible algorithms. My knowledge doesn't have that property. So it's a little bit surprising.

Actually, the interesting takeaway from this work, which by the way, is in variational integrator, so you have nice energy conservation property, is that she was able to separate out two different notions of numerical stiffness. Oftentimes people think of integrators for this problem as being very stiff numerically, which is absolutely the case. In fact, the word stiffness comes from problems like this, stiff material.

What she found is that using the stable integrator for this specific version of elasticity, that's important in computer graphics domain is actually not quite as hard as we thought. But essentially, there's actually two different notions of what's called ill conditioning that happen in this. One is the time integrator itself. So think about forward Euler versus whatever. And the other is the root finding problem that you get by using a particular time integrator.

And then a lot of the mythology about these variational integrators is that they're hard because the time integrator itself is ill conditioned, has a big time step restriction, which you found is that's actually not the case specifically for this problem, but rather the challenges in actually implementing that time integrator because of the root finding. And so she came up with a really clever algorithm for optimizing this particular case and then showed that she could take much larger time steps than were in the past literature.

This strategy turns out to be a very common pattern in geometry processing. In fact, I was looking back at our research, and apparently we've got a lot of mileage out of basically one trick. Sometimes you don't get so lucky. You can't break your problem into two tractable things.

So maybe only one problem is tractable and the other one just isn't in which case, one thing that you can do is at the very least, view your problem as a function of the outer variable and then have an inner objective function, which is the minimum with respect to the other guy.

And so for example, over the last couple of years, we actually have a state of the art technique for yet another problem in graphics, which is something called skinning, which is an interesting combination of PDE and optimal control, where I'm given a 3D surface and my goal is to compute a partition of unity of that surface. So like a set of functions that pointwise adds up to 1, is smooth, and is localized on different parts of the domain.

Now, it turns out this problem, there's a really simple way to do it using Green's functions of Laplacian. So if you stick a delta function at each of the points of interest and then solve the Poisson equation with that thing on the right hand side, then it turns out you'll get something that satisfies all of your constraints for free, thanks to the maximum principle, which is cool.

The only problem is that that's a really useless algorithm in practice because it creates what's called a tent pole artifact, which in this community I think would be called an ill posed PDE, which is to say you shouldn't have a point constraint on a second order problem. So in practice, people use a technique called bounded by harmonic weights, which takes that problem, adds all the constraints you might want to add to it, and then solves a very high order optimization thing, which ends up being a quadratic objective with quadratic constraints and it takes hours to actually solve in practice.

My student, Yu, did a really beautiful thing, which is he showed that, OK, this harmonic weight technique, this one using a linear solve, is not very practical, but it does automatically satisfy all the constraints that make these other algorithms really difficult. But here's a fun observation. If I take this 3D model, I could deform it, solve the linear problem, and then deform it back, and I get a different partition of unity than had I solved it on the original thing.

In other words, if I change the geometry, I get a different solution to a classical linear problem. And so he ended up posing computing these skinning weights as an optimal control problem, which is cool, where essentially what you do is you say, OK, for every geometry you put on this 3D model, so if you're a Riemannian person, every dot product you can put on every triangle, you get a different solution to the linear harmonic equation.

So I'm going to optimize some secondary property over those solutions where my variable is the Riemannian metric of the surface itself. And this turns out to be extremely efficient and removes all of the constraints of the problem because it benefits from the maximum principle of the original domain. So it's a really clever rephrasing of this things that actually in his case, he just used gradient descent, and it was fine. He didn't even need some fancy higher order method.

Incidentally, I'm watching the clock, I think-- do we want to stop earlier? There was some-- I wasn't sure. All right. Well, let me know and I'll call.

So, briefly, I thought I'd mention actually two more strategies that are from the convex analysis world. Now, the first two, I think, are very classical techniques in numerical methods very broadly. The last two, I think, are more specialties of my research lab specifically. So I probably should have led with those. And instead I now have five minutes to cover them.

But in particular, there's a lot of really beautiful theory out there in optimization that tries to take a problem, which is really hard and non-convex, which certainly includes all the things I've told you about so far. Relax the constraints of the objective into some convex problem, solve that thing, and then basically do prayer and hope that the thing that you got also solves the original problem. And of course, there's a lot of beautiful theory that gives conditions under which that can happen.

And the interesting thing is that, I think, this is an idea that arguably arose from the operations research style approach to optimization is also very much applicable to these PDE constrained optimization problems. It leads to a very different class of algorithms in this domain.

So as an example of yet another local optimum in geometry processing, here's a good one, which is computing minimal surfaces where the input is the boundary of some surface. And your job is to find a surface whose boundary is this thing with minimal surface area. It's very classical problem. Obviously, here, for example, there are two local optima that are in, this case, discretely separated from one another, where I can connect this boundary as a toilet paper tube or as two circles. And one of these things has a lot less surface area than the other.

Here's a fun brain twister is to think about what happens as you move those circles farther apart, a discrete flip occurs. In fact, you can actually write a convex relaxation of this problem. We'll talk about that in a minute.

So in any event, in this very different world of optimization, essentially, there's this big distinction between problems that are nicely bowl shaped, which we'll call convex, and problems that are very much not bowl shaped, that are not convex and have lots of local optima. And so there's this kind of interesting procedure that's arisen in optimization community starting with a weird non-convex problem, relaxing the constraints, for example.

So here I'm going to assume my objective function is linear. And I have a really nasty set of constraints. Turns out you can always do that. I'm going to take the constraints and try to find their convex hull. And the thing you can convince yourself is so long as you have a linear objective function, then the optimal solution to your problem always lives on the convex hull of your constraints.

So you can actually see that in this picture right. So for example here the linear objective, I guess, goes from blue to purple. And the optimal point in my objective is here. If I fill in the inside of my constraint set, then it's still there. The only issue is that it's often very, very difficult for a high dimensional problem to find the convex hull. So in reality, we find some convex that contains our constraints. And we hope that it's not too big. And that's this procedure of convex relaxation.

And there's a lot of really beautiful theory out there that tries to give strategies in some sense for how to find that object on the right hand side that some where between tractable computationally and also small enough to contain the problem you're trying to solve. And so our group has applied this to all kinds of fun problems. I don't have enough time to give you the details, but I'll briefly give you a bit of intuition.

So one classical problem in geometry is computing geodesic distance, basically shortest path along a surface. So I've fixed some source point, and I want to know the distance from that guy to everywhere else, constraint to move along the surface. From a PDE perspective, this thing satisfies a differential equation called the eikonal equation. Fun fact. This is the Greek word for image, so you shouldn't capitalize it despite the literature.

And it satisfies this differential equation here, which is, if you have this distance function, you take its gradient, you take its norm, you should get that that's identically equal to 1, at least away from singular points. My colleague Keenan Crane at CMU explains this PDE in a funny way. It's saying that distance is changed at a rate of 1 unit of distance per unit of distance, which is absolutely the case.

It is also extremely nonlinear because this norm notation is containing a square root. And so one thing that you can do is you can look at functions that you can call sub-eikonal, roughly Lipschitz. And this is a convex set. If I take two of such functions that satisfy that constraint, then it turns out their average does as well.

And so this allowed us to propose a whole class of algorithms for computing geodesic distance, where you look at the things that satisfy the condition on the right hand side. And actually, it turns out among those, the function, which is 0 at the source point and maximizes point wise, is actually the geodesic distance function. This is true in graphs too, by the way.

And this allows you to basically link convex optimization to this class of problems that's somewhere between numerical PDE and computing shortest paths, which is a very different class of techniques, for example, from fast marching, which is the standard answer in this domain. We've also applied these tricks in other areas.

So for example, something that we definitely don't have time to dig into is in computer aided design, your services aren't composed of triangles, they're composed of higher order polynomials. And so even computing closest points becomes a non-convex, weird, crazy problem. Our friend Pablo Parrilo in this department is an expert in a very different set of strategies called sum of squares relaxation, which takes polynomial problems and writes this hierarchy of convex things.

And actually, you can show that high enough in that hierarchy, eventually you're guaranteed to get the global optimum. Of course, the gotcha there is how high is a hard problem to answer for most things. But actually we had an undergrad, Zoe Marcia, in our lab that got so much mileage out of this because she made a really cool observation, which is for problems in computer aided design, for whatever reason, the level that you need to go to in the laser hierarchy is two.

And so actually, this is not just a fun theoretical object, but a very practical technique to get global optima of a lot of operations that are considered very hard to implement inside of a piece of CAD software.

And then finally, actually, even the minimal surface problem can be written this way. If you like this thing, there's some language from geometric measure theory that shows how you can relax the problem of finding a minimal surface with a prescribed boundary as actually minimizing a very particular choice of L1 norm on the space around your boundary, which allowed us to propose a really crazy convex optimization style technique for computing minimal surfaces. Basically, given a boundary shape and its Biot-Sarvart function.

And in fact, in this particular thing, which is a really interesting direction for future research, not only can you use this relaxation, we actually showed it's compatible with neural network parametrization of the domain of the problem, which is a really bizarre thing to do. You took a problem, relaxed it to something convex, and then use a very non-convex parametrization. And I think there's actually a very good reason for that, which is a fun topic for later.

Now, I'm pretty much out of time. So we're going to skip our last topic here, which is there's one more strategy, which if you're familiar with convex optimization is duality, where essentially for every convex problem, there's some dual problem basically in the Lagrange multipliers. And it turns out for a lot of problems in geometry, if you use a variational calculus perspective, you can derive a very similar calculation that solves different PDE in a very different shadow domain.

And that for a lot of problems in this particular space, there's a really beautiful set of duality that actually suggests new algorithms. So for example, in my old PhD thesis, an optimal transport was one example of this. And more recently, we showed that the dual of computing skinning weights, which is this classic problem in computer graphics that people just hadn't thought to apply this machinery to is actually just non-negatively squares after a lot of simplification, which is cool because that's an easy problem computationally.

And so now this is actually just a couple lines of code to solve these skinning weights rather than many hours and waiting for mosaic to converge. In any event, I should stop here. There's so many open questions.

For example, how do you take all of these beautiful structures we studied on mesh objects and make them work, for example, with neural fields and neural networks and pins and all these things that people care about today? And I think there actually are a lot of lessons learned from these domains that carry over to that space, but you have to do so in a very careful fashion. There's also nice ways to incorporate stochasticity sampling.

And these days, actually, our group has a postdoc, Ahmed Mahmoud, who is an expert on GPU hardware acceleration, which is a totally new one for me. At the end of the day, you can do all the math you want, but it's still implemented on this chip. And he's convinced me that even digging into, for example, the details of Cholesky factorization, the thing we think of as this black box, and understanding the dynamics of that procedure, specifically on a triangulated surface, can lead to accelerated algorithms that don't apply in the generic case, which is really cool.

He's a very brave human. I would have never thought to look inside. The thought of opening a piece of code for sparse Cholesky decomposition to me is just totally horrifying. But he just did it head first and now has 10x speedup over the generic library.

So in any event, I'm talking too much-- but hopefully, I've convinced you guys that geometry processing essentially can benefit from all these kinds of cool, custom built optimization techniques. There's all kinds of beautiful structures. This is one of these fields that combines observation from PDE, differential geometry, numerical analysis, optimization, convex analysis.

It glues them all together and moreover has this really frustrating set of clientele, which is artists who could care less if your algorithm has a beautiful property. They just want to make sure this thing gives them a result on some terrible input they should have never used. And so because of that, it's just such an interesting and fun area.

It is my pleasure to answer any questions that you might have. I know we're basically out of time. I think there's probably lunch, so I can hang out with you guys wherever. And my office is across the street. So thank you very much for your time. It's such a pleasure to come today.