Abstrakt. Nyligen påpekade Frumkin [9] att ingen av de välkända algoritmer som omvandlar ett heltalsmatris till Smith [16] eller Hermite [12] normal form är känd för att vara polynomiskt avgränsad i sin körtid. Faktum är att Blankinship [3] lade märke till – som ett empiriskt faktum – att mellanliggande tal kan bli ganska stora under standardberäkningar av dessa kanoniska former. Här presenterar vi nya algoritmer där både antalet algebraiska operationer och antalet (binära) siffror i alla mellanliggande tal begränsas av polynom i längden på indata (förutsatt att kodas i binär). Dessa algoritmer finner också multiplikatormatriserna K, U' och K' sådan att AK och U'AK' är Hermite och Smith normala former av den givna matrisen A. Detta ger det första beviset på att multiplikatorer med tillräckligt små poster finns.
Både Hermite och Smith normala former av ett heltal matris kan beräknas i starkt polynom tid REF.
Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}