FPGA implementation of the interior-point algorithm with applications to collision detection

Chih Hung Wu; Seda Ogrenci Memik; Sanjay Mehrotra

doi:10.1109/FCCM.2009.38

FPGA implementation of the interior-point algorithm with applications to collision detection

Chih Hung Wu^*, Seda Ogrenci Memik, Sanjay Mehrotra

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

The interior-point algorithm is a powerful method for solving a Linear Program (LP). A variety of optimization problems can be formulated as LPs. Often times the limiting factor of deploying an algorithm to solve LPs in a high performance system is the run-time efficiency. In this paper, we present the FPGA implementation of an affine interior-point algorithm that is designed to solve LPs. Specifically, we present the application of this algorithm to solving the LP for the real-time collision detection. The most important feature that distinguishes this particular algorithm from other collision detection methods is its superior ability to perform detection between pairs of objects undergoing fast rotational and translational motions.

Original language	English (US)
Title of host publication	Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009
Pages	295-298
Number of pages	4
DOIs	https://doi.org/10.1109/FCCM.2009.38
State	Published - 2009
Event	IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009 - Napa, CA, United States Duration: Apr 5 2009 → Apr 7 2009

Publication series

Name	Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009

Other

Other	IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009
Country/Territory	United States
City	Napa, CA
Period	4/5/09 → 4/7/09

Keywords

Inter-frame collision
Interior point
Linear programming

ASJC Scopus subject areas

Hardware and Architecture
Software

Access to Document

10.1109/FCCM.2009.38

Cite this

Wu, C. H., Memik, S. O., & Mehrotra, S. (2009). FPGA implementation of the interior-point algorithm with applications to collision detection. In Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009 (pp. 295-298). Article 5290897 (Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009). https://doi.org/10.1109/FCCM.2009.38

@inproceedings{d0f6a5eb1f8a4c5e868a67bc4ab20e26,

title = "FPGA implementation of the interior-point algorithm with applications to collision detection",

abstract = "The interior-point algorithm is a powerful method for solving a Linear Program (LP). A variety of optimization problems can be formulated as LPs. Often times the limiting factor of deploying an algorithm to solve LPs in a high performance system is the run-time efficiency. In this paper, we present the FPGA implementation of an affine interior-point algorithm that is designed to solve LPs. Specifically, we present the application of this algorithm to solving the LP for the real-time collision detection. The most important feature that distinguishes this particular algorithm from other collision detection methods is its superior ability to perform detection between pairs of objects undergoing fast rotational and translational motions.",

keywords = "Inter-frame collision, Interior point, Linear programming",

author = "Wu, {Chih Hung} and Memik, {Seda Ogrenci} and Sanjay Mehrotra",

year = "2009",

doi = "10.1109/FCCM.2009.38",

language = "English (US)",

isbn = "9780769537160",

series = "Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009",

pages = "295--298",

booktitle = "Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009",

note = "IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009 ; Conference date: 05-04-2009 Through 07-04-2009",

}

Wu, CH, Memik, SO & Mehrotra, S 2009, FPGA implementation of the interior-point algorithm with applications to collision detection. in Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009., 5290897, Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009, pp. 295-298, IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009, Napa, CA, United States, 4/5/09. https://doi.org/10.1109/FCCM.2009.38

FPGA implementation of the interior-point algorithm with applications to collision detection. / Wu, Chih Hung; Memik, Seda Ogrenci ; Mehrotra, Sanjay.
Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009. 2009. p. 295-298 5290897 (Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - FPGA implementation of the interior-point algorithm with applications to collision detection

AU - Wu, Chih Hung

AU - Memik, Seda Ogrenci

AU - Mehrotra, Sanjay

PY - 2009

Y1 - 2009

N2 - The interior-point algorithm is a powerful method for solving a Linear Program (LP). A variety of optimization problems can be formulated as LPs. Often times the limiting factor of deploying an algorithm to solve LPs in a high performance system is the run-time efficiency. In this paper, we present the FPGA implementation of an affine interior-point algorithm that is designed to solve LPs. Specifically, we present the application of this algorithm to solving the LP for the real-time collision detection. The most important feature that distinguishes this particular algorithm from other collision detection methods is its superior ability to perform detection between pairs of objects undergoing fast rotational and translational motions.

AB - The interior-point algorithm is a powerful method for solving a Linear Program (LP). A variety of optimization problems can be formulated as LPs. Often times the limiting factor of deploying an algorithm to solve LPs in a high performance system is the run-time efficiency. In this paper, we present the FPGA implementation of an affine interior-point algorithm that is designed to solve LPs. Specifically, we present the application of this algorithm to solving the LP for the real-time collision detection. The most important feature that distinguishes this particular algorithm from other collision detection methods is its superior ability to perform detection between pairs of objects undergoing fast rotational and translational motions.

KW - Inter-frame collision

KW - Interior point

KW - Linear programming

UR - http://www.scopus.com/inward/record.url?scp=74349118170&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=74349118170&partnerID=8YFLogxK

U2 - 10.1109/FCCM.2009.38

DO - 10.1109/FCCM.2009.38

M3 - Conference contribution

AN - SCOPUS:74349118170

SN - 9780769537160

T3 - Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009

SP - 295

EP - 298

BT - Proceedings - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009

T2 - IEEE Symposium on Field Programmable Custom Computing Machines, FCCM 2009

Y2 - 5 April 2009 through 7 April 2009

ER -

FPGA implementation of the interior-point algorithm with applications to collision detection

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this