{"entities":{"Q677132":{"pageid":678981,"ns":120,"title":"Item:Q677132","lastrevid":63513300,"modified":"2026-04-11T13:40:39Z","type":"item","id":"Q677132","labels":{"en":{"language":"en","value":"A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 994638"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$E5B2EE02-2A7F-4E27-95DA-1A862C76ADED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b0c8331a78e425376173a49b8fcb05ea3568927","datavalue":{"value":{"text":"A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q677132$16B561BE-5024-4BAC-B4B4-FB8645C1ABE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b714073bdee6c7008d63aad1bfbb9bcc9e5fcfe","datavalue":{"value":"0890.65038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$F72FCE46-296E-4A52-9C03-CC8E52F05F72","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb8e2de89cb33e4ddfa6ba4982d33fda63a85007","datavalue":{"value":"10.1016/0024-3795(95)00743-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$7906292B-82F6-43C0-A6A7-32A395BBCDD3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"102e902a13408b9bdc8c485f3ac9bf42b3cfa780","datavalue":{"value":{"entity-type":"item","numeric-id":412207,"id":"Q412207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$09ED3193-B62C-451B-97A3-A3FD468759D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"26e0993fc39df2c483354ce491d369a5b4e349a3","datavalue":{"value":{"entity-type":"item","numeric-id":372873,"id":"Q372873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$B1AB888A-0337-42BB-A624-198242898133","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$484CACAD-16BC-4A14-93D3-2EE3969298CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24fb4fe71a2595983b723d9da5040cfe01165fe6","datavalue":{"value":{"time":"+1998-02-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q677132$21C0D5BE-DD5E-4C13-9053-78AECF3A9520","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b7da77f8a1ca42ee498dfd501d8227471a126c8","datavalue":{"value":"A fast Las Vegas sequential algorithm for computing the Smith normal form of a square nonsingular matrix \\(A\\in{\\mathbb{F}}[x]\\) is presented. \\({\\mathbb{F}}[x]\\) denotes a field. A Las Vegas algorithm means that an incorrect result will never be returned, but the algorithm may fail with small probability and requires repetition. The key step is preconditioning \\(A'\\) of the input matrix \\(A\\). It avoids the usual technique of diagonalizing the input matrix with a succession of unimodular row and column operations. The main computation is the (nonunimodular) triangularization of a polynomial matrix of the same dimension and with similar size of entries as the input matrix.    The cost of one pass of the algorithm requires \\(O\\sim (n^5d(d+\\log|A|)\\log(|A|))\\) bit operations using standard integer, polynomial, and matrix arithmetic plus no more than \\(O(n^2)\\) trial divisions, multiplications, and gcd computations (where \\(|A|\\) bounds the magnitude of all integer coefficients in \\(A\\), \\(d\\) bounds the degree of entries of \\(A\\)). Using fast integer and polynomial multiplication, the algorithm requires an expected number of \\(O\\sim (n^3d(d+n^2\\log|A|))\\) bit operations which significantly improves previous complexity results. The correctness of the algorithm is proved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$F68DE0F4-BC3A-477B-A764-4A434E08854A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$B2B30DAC-6594-4203-974E-0A403C774810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$DDFD632D-3891-4678-BAE1-A55962BB5723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$40B32B0F-1726-42AB-9366-3B66655903E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"86467c42076cd02d03efdb91299b004ea1185418","datavalue":{"value":"15A21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$F7A5B2DA-2821-4248-8642-44804CA0A019","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1328a33fcb2a7fb0cdec41c013eb7b016b26948c","datavalue":{"value":"994638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$485FA7C3-C5FD-418C-8606-32967059CA61","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac114b5d8a78098b8aa8fc44237f76764506d509","datavalue":{"value":"Smith normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$F960ACEC-5EC0-4F27-9969-189D2DB7660B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fee8a58d43a11afee48e687af18b09d08ea36ede","datavalue":{"value":"Las Vegas probabilistic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$4317B339-D90B-480E-830D-ACCA3A77385C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dec9a4d9272b3066690a076188e8c04d09783753","datavalue":{"value":"complexity reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$B8FE7EC0-BD2D-4516-8F28-1E70B78D9032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c90073aa2d2bdf5d827a0d9d411af4ac6a98672","datavalue":{"value":"nonunimodular triangularization","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$CC1A0450-8A3C-48A2-8BC2-BD89D3270F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89708e03adfb7f6610af2bb8d51621e0550ccad0","datavalue":{"value":"polynomial matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q677132$48CE9AD3-E639-4A00-9944-8EFC78BD970A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f62228a5ef103a56a3b2ab18d746e6cdc0920111","datavalue":{"value":{"entity-type":"item","numeric-id":209077,"id":"Q209077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$2D453BD6-9B5A-4654-9F0D-2CE77259DFC2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$A04FBC60-939D-4B6E-9F5D-48CFDE574D5B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b32bb4fc631f359e3a8eaf0d9bf39a383ec6e2e0","datavalue":{"value":"https://doi.org/10.1016/0024-3795(95)00743-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q677132$9A0DE19E-B409-45EA-A91B-0C0EC61EDF3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"73ed8563faf2ef23d7ea9a192f1a0fd80a13ae38","datavalue":{"value":"W1976601425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677132$A4C08E04-E53B-4407-BA81-09F1DD77E1B5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a969d4ac0387643f87e037e42dffd6e635bc6c86","datavalue":{"value":{"entity-type":"item","numeric-id":5578437,"id":"Q5578437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$59100663-221F-4AFA-B7E6-448371974712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a71a4357e2d824bd207eb1c60585e9753d0e10e7","datavalue":{"value":{"entity-type":"item","numeric-id":5652123,"id":"Q5652123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$BC15705D-26A3-4B35-84B3-006208F536A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"446374df6c50565e89a26cde61b70240f20045f9","datavalue":{"value":{"entity-type":"item","numeric-id":3026176,"id":"Q3026176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$C3660954-B1F8-4816-97FA-B66A2785F0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ba27fba089b7d2f232445958a8b4c62809b01f5","datavalue":{"value":{"entity-type":"item","numeric-id":4120626,"id":"Q4120626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$C1869DE5-8EFC-43DF-9104-C8FEB4DD7F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c790a28a23b5ecff99b272336c89700604ca255","datavalue":{"value":{"entity-type":"item","numeric-id":3254327,"id":"Q3254327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$CEA15952-5331-4BDD-8174-EC4913FD3E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ba154389a204d2fe13cce852c6d6422d7912c2","datavalue":{"value":{"entity-type":"item","numeric-id":4023676,"id":"Q4023676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$403636A5-F865-4759-AF00-A2D5E65BA2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6885e5e56dca44e693c25716fc68ee62931eb074","datavalue":{"value":{"entity-type":"item","numeric-id":4234328,"id":"Q4234328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$E1061EA2-6A40-4853-8E99-1E2C7E833B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68dbf32c8d10bd8256ab1423df65a9bbe3aadf44","datavalue":{"value":{"entity-type":"item","numeric-id":5605894,"id":"Q5605894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$E8CE8CD1-5AEA-4C39-AADB-303DFBEA8243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03f1ddaba8285217bb41a356c810dd9d4f0f25b5","datavalue":{"value":{"entity-type":"item","numeric-id":5595961,"id":"Q5595961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$EDFBC838-D644-43B6-AC9C-27674282EB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3165438c92aed158e9ee66d8a5de489a8ab851f8","datavalue":{"value":{"entity-type":"item","numeric-id":1151859,"id":"Q1151859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$8C1101E1-CCC7-41C6-B1CA-48DC2ED45F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727079b56cd73b62009131634b9e239952aac993","datavalue":{"value":{"entity-type":"item","numeric-id":3802506,"id":"Q3802506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$8738513F-A78C-403E-B887-B8CAAF92B529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d98132e7646510fa9ffea4e34cefdc1068c5860","datavalue":{"value":{"entity-type":"item","numeric-id":5393358,"id":"Q5393358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$A8B1B262-6085-4464-8FFE-0A6CE65F32EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed54a63b9bb45697de6fabdc312b94b2d947d8f5","datavalue":{"value":{"entity-type":"item","numeric-id":803724,"id":"Q803724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$74F7E9EE-7465-40EB-92E7-6596C6975690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"135670d012bab6a5aca266dbc04a06e23fa8f267","datavalue":{"value":{"entity-type":"item","numeric-id":1082773,"id":"Q1082773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$FDE409AE-AA9F-4B5A-9F4F-66273401931B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3e841a2718df2f0c15920defa773b7a7538ca33","datavalue":{"value":{"entity-type":"item","numeric-id":5668937,"id":"Q5668937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$A3587669-9610-4F9D-8D00-382687EA3FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696056ff49d7c9804ae219e65f4a8593ba5a580c","datavalue":{"value":{"entity-type":"item","numeric-id":3796740,"id":"Q3796740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$795586DC-6AC4-4547-9611-1E6B6620B0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$C5BA915B-B9B0-4593-A60A-19F86B56D5D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0d25db474f232e9be4fa72538a7f5cfee2ff83","datavalue":{"value":{"entity-type":"item","numeric-id":1809087,"id":"Q1809087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$7EEF035F-5116-45CD-B517-21F2C18C52CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"005d97548feea2bd0edff2a2a91d81a8162f8910","datavalue":{"value":{"entity-type":"item","numeric-id":4234198,"id":"Q4234198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677132$D885E05B-AF43-4964-BF1F-AA6D0ADAFAD7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b7397c211e391505db1587d1c6e9f0eb7f07e7b","datavalue":{"value":{"entity-type":"item","numeric-id":4227282,"id":"Q4227282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3596c771c52de28b325bef01257f3af45f11ab43","datavalue":{"value":{"amount":"+0.8962590098381042","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677132$35B3DFA8-72CF-4F39-BE2C-987B8905441B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0f5f90701abe83baee7257b21f0dc7d0a56fe79","datavalue":{"value":{"entity-type":"item","numeric-id":5957090,"id":"Q5957090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9263f11ffa8970a1540b724db2649e01b8a95af1","datavalue":{"value":{"amount":"+0.8596101403236389","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677132$6C48F81F-44C9-4F09-A3EE-8C8C222F6C06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39bfed353755aa193af0edc8f0e3a334feb6dabe","datavalue":{"value":{"entity-type":"item","numeric-id":4227352,"id":"Q4227352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16c2417840d04f764c9392a1353bd3e8ecee6d71","datavalue":{"value":{"amount":"+0.8515784740447998","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q677132$5161A86B-F80E-4432-91B0-D4887062A470","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_fast_Las_Vegas_algorithm_for_computing_the_Smith_normal_form_of_a_polynomial_matrix"}}}}}