I think that's the same as when I said "I knew how to solve n-body systems with particle N^2/2 forces (corrected) with some quadtree or octree optimizations to get from n^2 to nlog(n)." . Or are you saying something different?
On Fri, May 5, 2023 at 2:58 PM Angel Edward <edward.an...@gmail.com> wrote: > Here’s another connection I had forgotten. Consider particles on a 2D > rectangle with 1/r^2 repulsion. If you break up the rectangle into smaller > rectangles in which particles can only stay in their own rectangles or move > to neighbor rectangles, the N^2 force calculation comes down to N log N, > same as the limit on good sorting algorithms. This technique came up when > we were using particles to form an isosurface in 3D. > > Ed > __________ > > Ed Angel > > Founding Director, Art, Research, Technology and Science Laboratory (ARTS > Lab) > Professor Emeritus of Computer Science, University of New Mexico > > 1017 Sierra Pinon > Santa Fe, NM 87501 > 505-984-0136 (home) edward.an...@gmail.com > 505-453-4944 (cell) http://www.cs.unm.edu/~angel > > On May 5, 2023, at 2:31 PM, Stephen Guerin <stephen.gue...@simtable.com> > wrote: > > Thanks Roger and Ed! > > I've spent some time with Ed and Frank discussing this and I've really > filled in some gaps in my knowledge of parallel algorithms. eg, I knew how > to solve n-body system with particle N^2/2 focus with some quadtree or > octree optimizations to get from n^2 to nlog(n). But the FFT transform on > laplacians solving Poisson equation was new to me and I can now see the > beauty. Today, Ed quickly threw out the Kronecker Operator/Product which > Frank knew but I didn't. Frank flashed me a wikipedia article > <https://en.wikipedia.org/wiki/Kronecker_product> on his phone with > symbolics that I couldn't immediately grok. But asking chatGPT to explain > the operator to a 3D graphics person I immediately got it and had the > benefit that I would usually implement this function with two inner loops > over rows and columnts instead of using Kronecker available in optimized > linear algebra/graphics libraries. Often this was happening under the hood > of my tools but didn't realize it. > > As a 3D graphics developer, understanding the Kronecker matrix can be very > useful. The Kronecker product is often used in computer graphics and > computer vision applications, such as texture mapping, geometric > transformations, and image processing. Here are a few specific ways in > which Kronecker matrix can be useful to a 3D graphics developer: > > 1. Texture mapping: The Kronecker product can be used to create > repetitive patterns in textures, such as brick walls, tiles, or grass. By > creating a base texture and applying a Kronecker product with a smaller > texture, a developer can create a seamless and repeating texture that > covers a larger surface. > 2. Geometric transformations: The Kronecker product can be used to > perform geometric transformations, such as scaling, rotation, and > translation, on 3D objects. By creating a Kronecker matrix with a > transformation matrix, a developer can apply the transformation to every > vertex of an object, resulting in a transformed object. > 3. Image processing: The Kronecker product can be used to perform > image processing operations, such as blurring, sharpening, or edge > detection, on 3D images. By creating a Kronecker matrix with a filter > matrix, a developer can apply the filter to every pixel of an image, > resulting in a processed image. > > In summary, the Kronecker matrix is a powerful tool that can be used in > various ways by 3D graphics developers. Whether it's creating textures, > transforming objects, or processing images, understanding the Kronecker > matrix can help a developer achieve their desired results more efficiently > and effectively. > > > > _______________________________________________________________________ > stephen.gue...@simtable.com <stephen.gue...@simtable.com> > CEO, https://www.simtable.com <http://www.simtable.com/> > 1600 Lena St #D1, Santa Fe, NM 87505 > office: (505)995-0206 mobile: (505)577-5828 > > > On Fri, Apr 28, 2023 at 7:50 PM Angel Edward <edward.an...@gmail.com> > wrote: > >> Most of my dissertation (1968) was on numerical solution of potential >> problems. One of the parts was a proof that some of the known iterative >> methods converged. The argument loosely went something like this. Consider >> the 2D Poisson equation on a square. If you use an N x N approximation with >> the usual discretization of the Laplacian >> >> u_ij = (u_i(j-1) + u_i(j+1) + u_(i_1)j + i_(j+1))/4 >> >> i.e, the average of the surrounding points, the problem reduces to the >> solution of a set of N^2 linear equations >> >> Ax = b >> >> where x in a vector of the unknown {u_ij} arranged by rows or columns, b >> is determined by the boundary conditions and the right side of the Poisson >> equation. The interesting part is A which is block tridiagonal. With only a >> small error A can be made block cyclic. You can then diagonalize A with a >> sine transform and I was able to use that for proofs. >> >> A few years later when the FFT came about, we realized that we could use >> the FFT to do the sine transform and the resulting numerical method was as >> least as efficient as any other method people had come up with. >> >> Ed >> >> Here’s a reference from 1986 that I think was based on paper at a Bellman >> Continuum >> >> ``From Dynamic Programming to Fast Transforms,'' E. Angel, J. Math. Anal. >> Appl.,119,1986. >> >> Ed >> __________ >> >> Ed Angel >> >> Founding Director, Art, Research, Technology and Science Laboratory (ARTS >> Lab) >> Professor Emeritus of Computer Science, University of New Mexico >> >> 1017 Sierra Pinon >> Santa Fe, NM 87501 >> 505-984-0136 (home) edward.an...@gmail.com >> 505-453-4944 (cell) http://www.cs.unm.edu/~angel >> >> On Apr 28, 2023, at 8:18 AM, Stephen Guerin <stephen.gue...@simtable.com> >> wrote: >> >> Special Unitary Groups and Quaternions >> >> Mostly for Ed from the context of last week's Physical Friam if you're >> coming today. >> >> Discussion was around potential ways of visualizing the dynamics of >> SU(3), SU(2), (SU1) that highlights Special Unitary Groups. (wiki link >> from Frank <https://en.wikipedia.org/wiki/Special_unitary_group>), and >> can we foreground how quaternions are used in this process. >> >> and a related bit on forces, I'm searching for ways to >> visualize/understand how FFTs with Poisson equation >> <https://www.codeproject.com/Articles/5308623/Solving-Poisson-Equation> >> are used to compute the forces from scalar fields (eg gravitational force >> from mass density, electric force from charge, etc) and if there's any >> relation to Special Unitary Groups. >> >> -S >> -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . >> FRIAM Applied Complexity Group listserv >> Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom >> https://bit.ly/virtualfriam >> to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> FRIAM-COMIC http://friam-comic.blogspot.com/ >> archives: 5/2017 thru present >> https://redfish.com/pipermail/friam_redfish.com/ >> 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ >> >> >> -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . >> FRIAM Applied Complexity Group listserv >> Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom >> https://bit.ly/virtualfriam >> to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> FRIAM-COMIC http://friam-comic.blogspot.com/ >> archives: 5/2017 thru present >> https://redfish.com/pipermail/friam_redfish.com/ >> 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ >> > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom > https://bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present > https://redfish.com/pipermail/friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ > > > -. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . > FRIAM Applied Complexity Group listserv > Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom > https://bit.ly/virtualfriam > to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com > FRIAM-COMIC http://friam-comic.blogspot.com/ > archives: 5/2017 thru present > https://redfish.com/pipermail/friam_redfish.com/ > 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/ >
-. --- - / ...- .- .-.. .. -.. / -- --- .-. ... . / -.-. --- -.. . FRIAM Applied Complexity Group listserv Fridays 9a-12p Friday St. Johns Cafe / Thursdays 9a-12p Zoom https://bit.ly/virtualfriam to (un)subscribe http://redfish.com/mailman/listinfo/friam_redfish.com FRIAM-COMIC http://friam-comic.blogspot.com/ archives: 5/2017 thru present https://redfish.com/pipermail/friam_redfish.com/ 1/2003 thru 6/2021 http://friam.383.s1.nabble.com/
