/sci/ - Science & Math » Thread #14016366

63KiB, 720x289, sparse.jpg

View Same Google iqdb SauceNAO

/nmg/ - Numerical Mathematics General

Anonymous Sun 26 Dec 22:30:37 2021 No.14016366 View Reply Original Report

Quoted By: >>14016572 >>14016622 >>14016912 >>14019565 >>14022499

Sparse matrices edition
Previous: >>13984900

Some links:
>good first source into the topic
http://numerical.recipes/book/book.html
>video series on discrete diff geometry:
https://www.youtube.com/playlist?list=PL9_jI1bdZmz0hIrNCMQW1YmZysAiIYSSS
>please mention any additions you deem worthwhile

Discussion suggestion:
>GPU programming for numerical math: have you ever used gpu programming in order to solve a numerical problem?, if so, share the details
>linear systems: Have you ever had the fortune of stumbling into a problem whose solution involved a system which converged in $O(N)$ iterations?

Anonymous

Anonymous Sun 26 Dec 2021 23:39:06 No.14016572 Report

Quoted By:

>>14016366
Bump

Anonymous

Anonymous Sun 26 Dec 2021 23:52:15 No.14016622 Report

Quoted By:

>>14016366
I briefly skimmed the first video on discrete differential geometry. Does he end up talking about applications to the Ising model (he has a video of it as motivation)?

Anonymous

Anonymous Mon 27 Dec 2021 01:41:27 No.14016912 Report

Quoted By:

>>14016366
bumping for interest and as a show of support

Anonymous

Anonymous Mon 27 Dec 2021 04:06:32 No.14017205 Report

Quoted By:

Bump

Anonymous

Anonymous Mon 27 Dec 2021 04:56:03 No.14017308 Report

Quoted By:

pity bump

Anonymous

Anonymous Mon 27 Dec 2021 06:42:10 No.14017531 Report

Quoted By: >>14017879

Fuck rounding error. IEEE floating point is a sin.

Anonymous

Anonymous Mon 27 Dec 2021 09:21:38 No.14017879 Report

Quoted By:

>>14017531
As someone who has had the disfortune of working with fixed point arithmetic, you have no idea how good you have it lol

Anonymous

Anonymous Mon 27 Dec 2021 17:38:15 No.14019565 Report

Quoted By: >>14019821

>>14016366
All right, finally a new thread, I very much enjoyed the last one.

Who knows a fast way of computing A*inverse(B)*C where A, B, C are sparse banded matrices?

Anonymous

Anonymous Mon 27 Dec 2021 18:31:01 No.14019821 Report

Quoted By: >>14020186

>>14019565
Look into the scipy.sparse library in python, they have methods for handling sparse matrix products

Anonymous

Anonymous Mon 27 Dec 2021 19:36:58 No.14020090 Report

Quoted By: >>14021398

1+1+=3

Anonymous

Anonymous Mon 27 Dec 2021 19:59:48 No.14020186 Report

Quoted By: >>14020997

>>14019821
I for got to mention, I am working in matlab (this multiplication is part of a way larger program that cannot be easily transitioned into anything else).
I have player around with the ordering of multiplications, differences of time consumed are negligible. I have also tried pre-inverting B (this type of multiplication with different A and C matrices has to be done several times in each iteration of the model), so far this is the best I could come up with speed-wise (computation time decreases), but am worried about memory issues (inverse of B is >90% full and this could cause out of memory errors when the size of the model domain (=the size of B) becomes large for more complex problems). Whats interesting is that the overall result of this multiplication is fairly spare despite the middle matrix being almost full.
I have also looked into faster algorithms for inversion of my specific matrix type, but it doesnt seem to improve speed much, guess matlab has this part already optimized.
Also, all matrices in question are block matrices (can be partitioned into blocks of equal size)

Anonymous

Anonymous Mon 27 Dec 2021 21:00:26 No.14020454 Report

Quoted By:

bump

Anonymous

Anonymous Mon 27 Dec 2021 22:45:38 No.14020997 Report

Quoted By: >>14022497

>>14020186
Well it sounds like you have the initial things sorted out (using specific methods for sparse matrices, using the correct functions etc)
Honestly, without more detail, it's hard to help, given that there could be quite a few things going on.
Care to share the problem with more detail?

Anonymous

Anonymous Tue 28 Dec 2021 00:32:30 No.14021398 Report

Quoted By:

>>14020090
Error: lvalue of assignment is a literal (int).
1+1+=3
^ (Here)

Anonymous

Anonymous Tue 28 Dec 2021 00:39:58 No.14021421 Report

Quoted By:

DDG video was interesting but I ended up just wanting to do regular differential geometry. I think I'd manage anyway, but should DG or Top come first?

Anonymous

Anonymous Tue 28 Dec 2021 07:55:35 No.14022497 Report

Quoted By: >>14022693

>>14020997
I might, what details would be necessary?

Anonymous

Anonymous Tue 28 Dec 2021 07:56:53 No.14022499 Report

Quoted By: >>14022504

>>14016366
God damn this thread is shit

Anonymous

Anonymous Tue 28 Dec 2021 07:59:31 No.14022504 Report

Quoted By:

>>14022499
God damn you are shit

Anonymous

Anonymous Tue 28 Dec 2021 09:40:23 No.14022693 Report

Quoted By: >>14022768 >>14023896

>>14022497
Are you trying to solve a linear system or do you just need to multiply the matrices ?
Why do you need to multiply the matrices ?
What's the structure of the matrices exactly?
Any detail that could help pinpoint a suitable heuristic

Anonymous

Anonymous Tue 28 Dec 2021 10:13:45 No.14022768 Report

Quoted By:

>>14022693
>Are you trying to solve a linear system or do you just need to multiply the matrices?
I just need to multiply the 3 matrices. The product of their multiplication is a different matrix which is then used for something else down the line
>Why do you need to multiply the matrices?
This multiplication is an update procedure - it updates a certain matrix. These updates are done multiple times and the matrix after the final update is the one that is used to solve a linear system. I have identified that the update procedure (the 3 matrix multiplication) is the speed bottleneck in my code. The final linear system solution is not a problem.
>What's the structure of the matrices exactly?
I will post an image later, cant now, but they are all banded block matrices

Anonymous

View Same Google iqdb SauceNAO matrices.png, 105KiB, 1040x2493

Anonymous Tue 28 Dec 2021 16:15:47 No.14023885 Report

Quoted By: >>14023896 >>14023964 >>14023980 >>14024033 >>14024215

>>140226

A*inv(b)*C is the thing I am trying to accelerate because it is the bottleneck in my code in terms of processing time.

In pic, the distribution of nonzeros in my matrices as returned by the function "spy". It is also important to note that although A and C seem like they are related through some symmetry operation, they are not - the numbers in them are different, they just have a distribution of numbers that gives the illusion of symmetry

The inverse of B is nearly (>99%) full

As stated before, they have a block structure (can be subdivided into blocks) and the structure of the blocks and the matrices themselves remains unchanged while increasing the size of the grid.

I have already tried different techniques in linear operations to arrive at the result of the multiplication (using / and \ to replace the slow inv(), playing around with order of multiplication, etc), but the fastest way was pre-inverting B.

Pre-inversion is generally not advisable because inverses of sparse are usually full (as is in my case) and that causes memory problems for large problems, but for small to mid-sized problems I have found it to decrease computation time overall.

Any ideas/tips to dot his in a better way? You seem knowledgeable/interested in this. I am working in MATLAB 2021a

Anonymous

Anonymous Tue 28 Dec 2021 16:17:01 No.14023896 Report

Quoted By:

I meant to reply to this >>14022693 with this >>14023885

Pseudonymous

Pseudonymous Tue 28 Dec 2021 16:30:47 No.14023964 Report

Quoted By: >>14023990 >>14024215

>>14023885
It's been a while since I worked on this kind of thing, but:
Is B symmetric? If so, how does the run time for Cholesky factorization compare to the time to compute the inverse?

Anonymous

Anonymous Tue 28 Dec 2021 16:33:27 No.14023980 Report

Quoted By: >>14024003 >>14024215 >>14024365 >>14024566

>>14023885
well ok this is actually interesting.
The issue is that without a doubt your inverse will be full, so preinverting is always going to slow you down.
have you tried diagonalizing B?
what representation are you using for the matrices? csr, csc, etc?

Anonymous

Anonymous Tue 28 Dec 2021 16:36:37 No.14023990 Report

Quoted By:

>>14023964
have not tried factorization yet (as I understand it would require 2 actions afterwards, so shouldnt increase speed, would it?), but will give it a go

Anonymous

Anonymous Tue 28 Dec 2021 16:40:29 No.14024003 Report

Quoted By: >>14024236

>>14023980
no, B is not symmetric (it might be in some special cases, but is not symmetric in the general case)
I have not tried diagonalizing because I thought extra actions would only increase runtime, no?
>what representation are you using for the matrices? csr, csc, etc?
what are these/what do they mean? Im kind of a noob in linear algebra

Anonymous

Anonymous Tue 28 Dec 2021 16:50:19 No.14024033 Report

Quoted By: >>14024059

>>14023885
Just curious, what kind of problem is this? Is it a real world problem or purely mathematical one? I'm still new to numerical things so I can't think of any problem that uses 200x200 matrixes to solve. It looks like it's kind of linear system but doesn't complex problem is better suited for nonlinear (hence, it should not be matrix math) system?

Anonymous

Anonymous Tue 28 Dec 2021 16:53:05 No.14024043 Report

Quoted By: >>14024052

I dont want to learn any advanced NM, what library should I use?

Anonymous

Anonymous Tue 28 Dec 2021 16:55:16 No.14024052 Report

Quoted By: >>14024108

>>14024043
What language?

Anonymous

Anonymous Tue 28 Dec 2021 16:57:11 No.14024059 Report

Quoted By: >>14026140

>>14024033
this is a real world electromagnetics simulation. the matrix sizes are 3*nx*ny

Anonymous

Anonymous Tue 28 Dec 2021 17:09:09 No.14024108 Report

Quoted By:

>>14024052
R and MATLAB

Anonymous

Anonymous Tue 28 Dec 2021 17:35:18 No.14024215 Report

Quoted By: >>14024236

>>14023885
>>14023964
>>14023980
Also, the matrix is filled with complex numbers, almost forgot about that (dont know if it is important)

Anonymous

Anonymous Tue 28 Dec 2021 17:40:08 No.14024236 Report

Quoted By: >>14024374

>>14024003
>>what representation are you using for the matrices? csr, csc, etc
These mean which representation system you're using to well, represent your sparse matrix. csr means you're saving the nonzero elements ordering by row, csc by column and so on.
You are using one of these right ?

>>14024215
This is actually important,but you told me the matrices weren't symmetric so I'll assume they're not hermitian

Anonymous

Anonymous Tue 28 Dec 2021 18:11:21 No.14024365 Report

Quoted By:

>>14023980
I know diagonalization can be used for raising matrices to a large power, but not sure if it can be used for inversion/multiplication. Can it also be beneficial in this case?

Anonymous

Anonymous Tue 28 Dec 2021 18:14:33 No.14024374 Report

Quoted By:

>>14024236
ordering in matlab seems to be row first, column second

Anonymous

Anonymous Tue 28 Dec 2021 18:51:09 No.14024566 Report

Quoted By:

>>14023980
read up on diagonalization, seems like it wouldnt be applicable well in my case (turns out matlab diagonalizes a matrix by eigendecomposition and I tknow from experience this operation scales very poorly)

Anonymous

Anonymous Tue 28 Dec 2021 22:03:33 No.14025456 Report

Quoted By:

bumping for actual scientific discussion on /sci/

Anonymous

Anonymous Tue 28 Dec 2021 22:55:24 No.14025698 Report

Quoted By:

>tfw too brainlet to understand symplectic integrators

Anonymous

Anonymous Wed 29 Dec 2021 00:27:37 No.14026140 Report

Quoted By:

>>14024059
That's too vague. Can you explain more in detail? What kind of simulation?

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches