WEKO3
アイテム
Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case
http://hdl.handle.net/2261/00074088
http://hdl.handle.net/2261/000740884efa100c-cc1a-47e2-97fa-c8af933aa4fb
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case 2015.pdf (507.4 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-12-14 | |||||
| タイトル | ||||||
| タイトル | Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源 | http://purl.org/coar/resource_type/c_6501 | |||||
| タイプ | journal article | |||||
| 著者 |
IMAI, Hiroshi
× IMAI, Hiroshi× SUPPAKITPAISARN, Vorapong |
|||||
| 著者所属 | ||||||
| 著者所属 | the Graduate School of Information Science and Technology, The University of Tokyo | |||||
| 著者所属 | ||||||
| 著者所属 | the Global Research Center for Big Data Mathematics, National Institute of Informatics | |||||
| 著者所属 | ||||||
| 著者所属 | ERATO Kawarabayashi Large Graph Project, JST | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | In this paper, we improve a width-3 joint sparse form proposed by Okeya, Katoh, and Nogami. After the improvement, the representation can attain an asymtotically optimal complexity found in our previous work. Although claimed as optimal by the authors, the average computation time of multi-scalar multiplication obtained by the representation is 563/1574n+o(n)≈0.3577n+o(n). That number is larger than the optimal complexity 281/786n+o(n)≈0.3575n+o(n) found in our previous work. To optimize the width-3 joint sparse form, we add more cases to the representation. After the addition, we can show that the complexity is updated to 281/786n+o(n)≈0.3575n+o(n), which implies that the modified representation is asymptotically optimal. Compared to our optimal algorithm in the previous work, the modified width-3 joint sparse form uses less dynamic memory, but it consumes more static memory. | |||||
| 内容記述 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | Special Section LETTER (Special Section on Discrete Mathematics and Its Applications) | |||||
| 書誌情報 |
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences 巻 E98-A, 号 6, p. 1216-1222, 発行日 2015-06-01 |
|||||
| DOI | ||||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | 10.1587/transfun.E98.A.1216 | |||||
| 権利 | ||||||
| 権利情報 | copyright©2015 IEICE | |||||
| 著者版フラグ | ||||||
| 値 | publisher | |||||
| 出版者 | ||||||
| 出版者 | Institute of Electronics, Information and Communication Engineers | |||||
| 関係URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://search.ieice.org/ | |||||
