arrays - Compact storage coefficients of a multivariate polynomial -



arrays - Compact storage coefficients of a multivariate polynomial -

the setup

i writing code dealing polynomials of grade n on d-dimensional variable x , ran problem others have faced in past. such polynomial can characterized coefficients c(alpha) corresponding x^alpha, alpha length d multi-index specifying powers d variables must raised to.

the dimension , order general, known @ compile time, , high n = 30 , d = 10, though not @ same time. coefficients dense, in sense coefficients non-zero.

the number of coefficients required specify such polynomial n + d take n, in high dimensions much less n^d coefficients fill cube of side length n. result, in situation have store coefficients rather compactly. @ price, because retrieving coefficient given multi-index alpha requires knowing location.

the question

is there (straightforward) function mapping d-dimensional multi-index alpha position in array of length (n + d) take n?

ordering combinations

a well-known way order combinations can found on this wikipedia page. briefly order combinations lexically can count number of lower combinations. explanation can found in sections ordering combinations , place of combination in ordering.

precomputing binomial coefficients speed index calculation.

associating monomials combinations

if can associate each monomial combination can order them method above. since each coefficient corresponds such monomial provide reply you're looking for. luckily if

alpha = (a[1], a[2], ..., a[d])

then combination you're looking is

combination = (a[1] + 0, a[1] + a[2] + 1, ..., a[1] + a[2] + ... + a[d] + d - 1)

the index can readily calculated formula wikipedia page.

arrays algorithm math

Comments

Post a Comment

Popular posts from this blog

Delphi change the assembly code of a running process -

Delphi change the assembly code of a running process - i'm trying alter address 00741fa5 has push test.009e721c . alter push test.009e71c8 . procedure callback; asm force $9e71c8 end; procedure tform2.btn1click(sender: tobject); var ppid :dword; pprocess : cardinal; begin getwindowthreadprocessid(findwindow(nil,pchar('test')), @ppid); pprocess := openprocess(process_all_access, false, ppid); injectasm(pprocess, $741fa5, 10, integer(@callback), 0); end; here injectasm function (with error checking) function injectasm(process: longword; injectaddress, injectsize, codeaddress, codesize : integer): pointer; var csize, rsize : integer; replaced : array of byte; jmp : array [0..4] of byte; jmpaddress : integer; nopv : byte; : integer; nbr: ulong_ptr; begin //injectsize must equal or greater 5, because need space our //(far) jmp wwxxyyzz instruction //if there's no space, inject in place of few instructions if injectsize ...
Read more

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) -

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) - hello have problem hibernate , jackson. have 2 pojos @entity @table(name = "users") public class user implements serializable { static final long serialversionuid = 4235637833262722256l; @id @generatedvalue private int id; @column(name = "creation_date") private date creationdate; @column(name = "first_name") private string firstname; @column(name = "last_name") private string lastname; @version @column(name = "version") private int version; @column(name = "e_mail") private string email; @column(name = "enabled") private boolean enabled; @column(name = "login") private string login; @column(name = "password") private string password; @jsonmanagedreference("role") @onetomany(mappedby = "user", cascade = cascadetype.all,fetch = fetchtyp...
Read more

C++ 11 "class" keyword -

C++ 11 "class" keyword - i've started using c++ 11 little bit more , have few questions on special uses of class keyword. know it's used declare class, there's 2 instances have seen don't understand: method<class t>(); and class class_name *var; why precede typename keyword class in first example, , keyword pointer in sec example? that known elaborated type specifier , necessary when class name "shadowed" or "hidden" , need explicit. class t { }; // love of god don't t t; t t2; if compiler smart, give these warnings: main.cpp:15:5: error: must utilize 'class' tag refer type 't' in scope t t2; ^ class main.cpp:14:7: note: class 't' hidden non-type declaration of 't' here t t; ^ if class not defined, deed forwards declaration. for example: template <typename t> void method() { using type = typename t::value_type; } method...
Read more