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: > 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. > 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. > 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 <mailto: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 > <mailto: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 >> <mailto: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 >>> <mailto: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/
