Structured Arrays

Hello everyone, My name is Devendra Kapitiya and I'm the manager of calculus and algebra at Wolfram. Welcome to this talk on structured arrays, which is a very highly developed area of Wolfram language. Now in this talk I'd like to present work done by Yan Mangeldan, primarily as the main developer for the project and with me and other people, senior developers, helping along. But this is a project that's been a dream for us to do for a long time. And then about a year and a half ago, we started working seriously on it, most specifically on structured matrices rather than structured arrays in general. But then we made excellent progress. So it looked like a good time to talk about what's happened in the last year and a half or so. And what I'll do today is to give you the general framework of structured Radius and show you how they are kind of somewhat different from the usual lists that we know in the Wolfram language. And then once that is done, then after that I'll go on to the actual examples in which I'll have things like, you know, the, the identity matrix, permutation matrix, the Vandermonde matrix, Fourier matrix and orthogonal matrices. So the idea is to give you a balance between a theory and the example, just to show you how powerful this whole framework is and how well it fits into the modern way of doing linear algebra. So Yan is Yan, and he will probably make a few comments as well because he has done a lot of work and I'll be doing the presentation itself, but do feel free to ask questions and we'd love to hear what you think about this very, I would say, elegant piece of functionality that's developed over the last few years. So let me begin now by talking about structured arrays. So structured arrays are recently added feature like version 13.1, roughly, and they actually help you to make things much more compact. Just to give an idea, the typical entity matrix has got five rows and five columns, but if you say target structure goes to structured, then you get back just this summary box with some indication of what the entries look like. And that's really convenient. Think about, I need a Matrix of order 10 to the power 4 or better still 10 to the power 9. Good luck with trying to do that in some earlier version. So if you compare that with the list version over here, which is what was there all along and still there right now. We can't afford to change people's code. So this is what you'd see without the target structure option over here. So the point we hear that you can either have the list version or you can have a structured version. The structured version is really much more useful. That is our claim for today's presentation. Okay, so it's not like the first time we've had a new kind of array in the language. In fact, going back to version 4, we had packed arrays, but they're much more for numerical efficiency, very mysterious and a little hard to figure out what they were doing. But the first formal kind of array we had were these so called sparse arrays. And they were designed to deal with problems where you have large matrices with very few non zero entries. So these matrices required arrays, more generally required that you have a sparse structure, which would then encode the non zero values and not worry about anything else at all. Okay, so this was the sparse array moment. And then a little later on version nine, we had symmetrized arrays. So you can see you can do tightrope symmetry and you can symmetrize array over here. But these were much more in line with modern tensor algebra and calculus, because in those parts of science and mathematics one is concerned with symmetrizing objects. And in very extreme cases only symmetric things matter. Okay, so these, these are the kind of predecessors to the current structured array framework. Okay, so the point over here that we have had the list structures forever. So we need a new option in 13.3 to deal with it. And that's what you just saw in the previous slides, the target structure option. So target structure is an option for linear algebra functions that allows you to decide what kind of result you want from your function. Okay, so here is somewhat terse language to show which result matrices actually support target structure. Now it looks like a big list, but there are some differences. Okay, the new matrices like this one, Cauchy matrix, or block, diagonal, etc. Actually have the target structure set to structured by default. The older matrices, like diagonal matrix, for example, or more recently rotation matrix, will have a target structure set to kind of the list version, dense version by default, and then you must manipulate accordingly. But you can go back and forth between the list version and other versions using the target structure options. So I think the target structure option is kind of a wonderful thing, which we have had since last reason now it's going to become even more powerful in version 14. Okay, so with that background, let's now talk about are these structured arrays different from lists? Well, they look different, but for all practical purposes you can work with them as you would with any ordinary list. So here the Fourier matrix from, you know, the typically fast forwardier, transfer, whatever 28 one we need over here. And the matrix plot over here is just what you'd see with the list version. So Fourier matrices will work whether you're working with the dense version or the structured version. Okay, so there's no need to worry about will my code work or not. It will continue to work just as before. So question is, why would you want something like a structured array? Well, first of all, they definitely in general take less storage than on list. I said think of any matrix of size, let's say 10,000. So you need 10,000 rows and 10,000 columns to store versus just storing the order of the matrix. That's really, really much simpler and less storage. And of course there'll be cases where the storage is not such a big issue, but there'll be cases also where it's kind of half better in some sense. Like in a symmetric matrix way, store half it and the system figures out what the other half is. But, but more importantly, once we know that your matrix is structured of a particular type, you know, whatever it might be, then we can actually design algorithms and then they'll take less time, memory, etc. Because of these specialized algorithms. I'll show you example where these algorithms actually work brilliantly. So put together, this notion of storage and algorithms is itself a very compelling reason to have these structured arrays in the system. So as an example here, you're the anti mix of size division 10,000. So 10,000. Okay. And if you actually find out in the structured form, it looks nice and neat, but if you would actually do the normal of this, which I mean convert it to a list, gosh, that's going to be huge. Okay, and if you compare storage, you won't take 0.392 kilobytes in the first case, in the structured case, just that box, summary box, and 8,000 kilobytes. That means that really things which were not possible and not possible almost for silly reasons are now working wonderfully well thanks to the structured area framework. Okay, so I think that we really have managed to get quite a lot of mileage out of this already. So then the question is, okay, about storage, how about actual computation? Well, anyone with basic matrix knowledge knows that a determinant of an entity matrix is just one. So of course if you ask a structured version, it'll tell you the answer is one in a very, very tiny amount of time. If you ask the list version, it knows nothing. It take almost 1 1/2 seconds to figure out something that anyone could have answered. So In a way it's dumber than the average user, which is not such a great thing for us. So clearly structures are important in this particular case of a compute the inverse, well, the inverse of ID matrix is again itself. So then that's quick. And the actual list version is much, much slower. And of course if you go to higher dimensions, things get much, much better or worse depending upon whether you're doing structured versions or the dense versions. Okay, so the other point is that these matrices, these structured arrays are actually, you know, they have self knowledge, they are self aware. So like a bit of AI. Okay, so if you construct this permutation matrix by telling it what the cycles are here, 165234, you get back a summary box. But that matrix now knows everything about itself. But before showing you that, let me explain this. If you don't, if you're not an expert on permutations. So the first row gets permit to six months. So you see this, there's one over here and then the second one to except so six goes fifth, etc. So the cycles are shown over here and the permutation matrix encodes those cycles. And you can ask it, okay, what are your properties? And it'll tell you quite quickly what it knows about itself. It knows lots of stuff about itself, including what it's good for. So structured matrices are self aware. You can query them at any point system and use them with great ease. Okay, you could also ask a specifically and say whatever permission cycle, it will just do that for you automatically. Okay, so I think that already you can see the power you got, better storage, better algorithms, more knowledge about the matrix and at any time when you query it. So the point over here is that we also have this property which I you saw implicitly that you have the property of structured algorithms. And what that does is that if you take a particular structured matrix and you try the property, it will tell you which functions it is optimized for. And in each case that might be a long or a short list, but you will definitely get some benefit or the other. Of course, permutation matrices are very, very simple. So one should have no difficulty working out various things over. And the other point is that it'd be unfortunate if something which should have been structured suddenly lose the structure. So let's say you do the chronicle product of over here, then you get back another permutation matrix. So we try and preserve the structure as we move around the system and perform operations. So that's kind of almost two more reasons to use Structured arrays. Okay, so the first example, let's take a Vandermon matrix. And in fact I recall we did a course on linear algebra at that time. These Vandermond matrices were implicit, but we didn't quite have them in the system at that time in a usable form. Okay, so you have the Vandermonde matrix, okay, in the matrix form. Okay, so it requires in this case a specification of a vector, right? X1, x2, x3, x5. And it's clear way that this got something polynomial about it. And so they appear in fact in interpolating polynomial problems, which is how actually we use them even in the standard course in linear algebra. So then what you can do is you can take these random matrices, take some data and fit a polynomial curve to it. So I think that this is a very standard operation. But doing with random one matrices is of course much, much more efficient and elegant. Okay, so the point we hear that for Vanderbond matrices, if you have, let's say a Vector of length 100, then storing this would be very, very easy compared to stalling, throwing the full matrix of order 100 by 100. Okay, so if you look over the quantities of, you know, memory use, it's 3.16 versus 80. So clearly you have a huge saving when you work in the structured world. Again in this case, okay, so there's a point over here is that your computation like you saw earlier on the antimatrix, will typically take a lot less time. So the transpose works quickly compared to the non structured version. If you're trying to linear solve, that works much faster as well. Now keep in mind that we are linear solve and other functions do have specialized support for certain class of matrices. So you don't always get the full benefit, but you can be guaranteed you get at least the same benefit from using the structured version. So linear algebra is a very well developed age of Mathematica. We've been world class forever. What this does is just puts the final layer on top of the whole functionality. Okay, so now let's move on to Fourier matrices. So Fourier matrix of course are kind of very, very important in applications. I once read that a very large fraction of Nobel prizes have been awarded to work rate with Fourier. So personally I work on symbolic computation with the symbolic Fourier transform and I know just how important that area is. But I guess where the real applications are to do with the discrete Fourier transform, or in particularly the fast Fourier transform, which actually is an implementation of the discrete Fourier transform. Okay, so there's a classic Algorithm Cooley and Q key, which is, you know, gives you a fast Fourier transform and it saves quite a lot of effort for you. It goes down from O to N log n for multiplication of Fourier matrices with vectors. Okay, so we have a very nice implementation of this fast Fourier transform in the Fourier function and it's used for the Fourier matrix computations as well. So clearly these Fourier matrices are the right way to go in many, many situations. And of course question is, why does FFT work? Well, the idea of 50. Well, there are different ways of looking it, but here's an example which shows that in fact what you do is you take a matrix for which you want to do the fast Fourier transform and you kind of, you know, you factorize it into different parts. And these are really simple parts, they are very sparse and in fact each row only has at most 2 non 0 entries. So there are many discussions of the literature by Van Loan and people that which I recommend you. But basically you have simpler matrices you factor into and permutation matrix. So each step very, very efficient. And that's how the fast Fourier transform works. Okay, so the link over here to Van Loans work is actually quite useful for understanding this in greater depth. So I think the Fourier matrices are actually a big thing for a lot of practical applications and we'd like to improve this area even more both symbolically and and numerically. So in a way, linear algebra lies at the heart of analysis and calculus, but in a very kind of quiet way, it's at the, at the bottom of most important things. Okay, so then I go on to these so called orthogonal matrices. So what's orthogonal mean? Your matrix, you multiply it by its transpose to get back the entity, then that's orthogonal. Ortho is just right angle. So you want basically a sequence of vectors which are at right angle and kind of length one. So that's an orthogonal matrix from a kind of basically orthonormal set. You get back this orthogonal matrix, a structured array. Okay, but the nice thing is in version 14 we not only have this new object orthogonal matrix, but we can also use it as an output from various other matrices. So in fact our goal was twofold. One is to build a library of structured matrices and secondly to then use them in different parts of the system. So for example, in version 14, which you still don't have, but it's almost done, if you do rotation matrix of an angle about some vector here, and you say target shell goes to orthogonal, you'll not get the list structure. You will get the actual structured array, which is orthogonal of course. Right. And of course you can then do a normal and look at the matrix if you prefer do that. Or a reflection matrix has got the same kind of property on Euler matrix. So we have a large number of built in matrices which will actually do this for for you in version namely they'll give back output which is much more intuitive and efficient. And perhaps the, I guess the very top goal for us was we have lots of these matrix decompositions and in each case there's a particular kind of output that's generated. So for example, QR will generate also a matrix upper triangle. But we couldn't see that earlier version. Now we can see target structure goes to structured and it'll do just that for you. So by looking at the structured output, it's more intuitive, much more powerful, much easier to use. So I think that that's one important decomposition occurs in you know, let's say least square approximation etc and then you go the singular most famous decomposition linear algebra. Yeah. So in fact this is, you know, Golub had something on this number plate which said, I think Professor SVD or something of that sort. So SVD is a big thing for linear algebra. And now we can get back the structured form of SVD in version 14. So you get back and also on diagonal and okay, so this is really nice for people who work with these decomposition. Of course, a lot of people do. Okay, so then over here just to do a little bit more work with orthogonal matrices. Where do they come from? So for example, they come from these matrix distribution which we developed some time ago. So there are parts of system which are now becoming more understandable due to these new structured matrices. So this is a matrix distribution. You convert to orthogonal matrix form and check that in fact the inverse is equal to the transpose. And in fact there are other properties. If you take the orthogonal matrices, you multiply them, you get another orthogonal matrix. And remarkably, even the Kronecker product of two orthogonal matrices is going to be another orthogonal matrix. Also I think, I'm not actually sure, but this probably depends upon them being square. Okay, so there's some work going on underneath to prove these things, but we leverage that to make things much, much nicer for everyone. So I think that this gallery of examples we began with identity went to permutation, Vandermonde, Fourier orthogonal. There are a few more coming in version 14 along with orthogonal. So there's symmetric, there's unitary and there's Hermitian. So those matrix together we have an impressive library of basic structured matrices for you to start working with. So I think this project has now reached maturity and it's a great time to celebrate what's happened and acknowledge the wonderful work that everyone's done in the team, our QA and all the other people who work so hard to help us out. So I think it's time to summarize and say that structured arrays are an efficient way to represent matrices with inherent structure. So if you know that your matrix can be specified easily, then try and use structured arrays with the target structure option, if you can. And then if your application can be done in terms of one of these matrix, of course you are very, very lucky because then things are going to work much more optimally. And of course that's the way that these matrix have been developed. Vandermonde, I think, was a student of Bezier, I think. So people like that have actually worked because although Cauchy I don't think did much here, it was just an exercise in one of his books. So people have done these for different reasons historically, but then today this is actually a very well developed area and we have some feeling of pride as we go on that we have actually made a big amount of progress over here. It's time to do a course, time to write a book, and Yan is going to do all that work. He's, you know, not speaking of the tree, but I think that he's the one who's going to take this forward. But many thanks to you all for supporting this adventure into linear algebra. I'm not a linear algebra person by profession, if you like, but I think of all the things we do here, this is the one that gives the most satisfaction. The feeling that we are close to the real world with this area of the Wolfram language. So with those words I'm going to say thank you all for all that you do for us and it's been great to have you here. We have some time for questions, maybe a few minutes, so we'll be happy to do that, unless Yan is already looking after them. But I think that this is a good, good feeling that we have right now about everything. Okay, so can you please. Yeah, I think mostly has been answered. Excellent. So looks like Yan's been very busy with answering questions. And so Structure is version version nine, actually. Yes. So Itay Seguev is, by the way, going to give an extant talk on matrix computation. He, of course, is close to his heart. I don't know when structured arrays were actually introduced. I believe that they were in and out. We kind of tried to hide them. That's my impression. But maybe I'm wrong on all this. Any case, I think that for the first time we are proudly proclaimed them. And that's all I know about all this, you know. Yes. So I totally agree. We've had things like quantity, arrays, etc. For a long, long time. Ah, I think Jan already answered that, that what are LU D composition. That's a tricky one, Peter. But we had something that we're working on. Yes. So we've been trying to get this done for some time. I really think we should do it. Yeah. So I think, Patrick, I tried to explain this as well that you know, we really would like to use structured matrices everywhere. We can't do it for obvious reasons that, you know, we'd have a legacy kind of list structure to preserve. But going forward we'd like to develop new matrices with structure right away and build the algorithm. But if you look at documentation, you see lots of examples where something works wonderfully with the structured version rather than with the list version. There's no dearth of examples over there. Exactly. So I think Gene Golub is quite an. As Diane Mangel points out that his number plate actually did have license plate did have something called svd. Gene Golub actually studied right here in champagne. So he's one of my inspirations for linear algebra. Okay, I think we have a few minutes more and we just keep it going. But if you need to leave for the talk, I know there's another talk which I'd like to tell 12, so feel free to do so. It's been great to have everyone over here. It's a wonderful feeling that, you know, people are so excited about linear algebra, which is exactly what we want to do. We think this is an important thing for us in the future. Timothy, that's a great question. That's exactly what Yan is going to work on now. We have paused development. We're going to work on a structured array book to help you learn this area. Okay. So that should be for 14. I don't know what to call it, but the version after 14. But you haven't seen 14, so how about the version after 14? Okay. But thank you for asking the question. It's a bit all a bit confusing right now. We have done our best. There is a guide page from where you can follow things but we'll do our best to make it better. Scott's asking question. I'm sure Jan will answer it. About the relationship between structured arrays and yeah. Okay, let's keep the talk going for a few minutes more for people to ask questions. Yeah, probably not much with compiler right now, but I think that that's again a good point actually that's not a terribly. It's actually important in a certain other direction. We have these centered interval matrices now and perhaps they can become structured matrices in the future. So we are thinking about how we can leverage the structured array functionality to do various things. But I won't tell you everything over there. Attend it. I stock to understand what performance improvements we are trying to do by understanding more data types, you know. So that should be an excellent talk. Do take the handout. Yes, Itay's talk is one hour, we'll all be there but he's thinking deeply about how we can take linear algebra to the next level by first reflecting on what we already had. It should be exciting stuff. You might want to consider buying a different kind of machine the next time you go to the store after listening to his talk. So sure, please be there. Msx the documentation is quite good. We have a linear algebra course which still doesn't cover the structure but it's kind of very useful. So do look at what we have to understand our linear functionality which I think is absolutely. So the question Peter, about. Yeah, so yeah, I'm saying yes, unit matrices are in version 14 so we have symmetric and then Hermitian, the complex cousin and then orthogonal and its complex cousin unitary. And of course if you're a quantum kind of guy, then person then you. Unitary means quite a lot in Hermitian means quite a lot to you. So those are nice names to have in system if not anything else. I should warn you that in some cases the structured versions were a little questionable because the system already knows about them but it just seemed right to have them available at top level. So it's the whole thing with performance. Who knows what worked better before. Okay, I think we will end in a minute but thank you all. I'm just so happy. Yes Peter, I'm glad that you think that, you know, train matrices, they should work nicely. If you have something to let us know about how they can improve, do let us know. We'd be thrilled to hear from you. Yeah, I guess it's really time to say final goodbye because we should be closing about half a minute but it's great to see all the excitement. It keeps us motivated and the feeling that yes, this is worth doing, this has been worth doing and we're going to more in the future.